006:升序数组找出和是target的两个数字,遍历数组,先假定第一个数字,然后第二个可以通过二分法逐步得到。
007:数组中和为 0 的三个数,先实现数组排序, 同样的先假定第一个数字位置i,第二个位置left和第三个数字位置 right可以通过三数之和与0的大小进行比较,其中若大于0,则右边的数字减1,若小于0,左边的数字减1,但如果只是这么做复杂度较大,同时需要去重。
两步去重:1.在当前满足三数之和是0的时候,比较 left和left++,right和right++ 是否相等
2.比较 i和i++处的位置是否相等
若相等,则直接continue,避免计入重复值和减少运算量。
java版本:
class Solution {
int[] arr=new int[2];
public int[] twoSum(int[] numbers, int target) {
int left=0,mid=numbers.length/2,right=numbers.length-1;
for(int i=0;i<numbers.length;i++){
left=i;
int tar=dfs(numbers,left+1,right,target-numbers[left]);
if(tar<numbers.length && numbers[left]+numbers[tar]==target){
arr[0]=left;
arr[1]=tar;
return arr;
}
}
return arr;
}
public int dfs(int[] nums, int left,int right,int target){
while(left<right){
int mid=left+(right-left+1)/2;
if(nums[mid]==target){
return mid;
}else if (nums[mid]>target){
right=mid-1;
}else{
left=mid+1;
}
}
// dfs(nums,left,right,target);
return left;
}
}
java版本:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> arr=new ArrayList<>();
Arrays.sort(nums);
int left,right,target,sum;
for(int i=0;i<nums.length-2;i++){
left=i+1;
right=nums.length-1;
while(left<right){
sum=nums[left]+nums[right]+nums[i];
if(sum>0){
right--;
continue;
}else if(sum<0){
left++;
continue;
}else{
ArrayList<Integer> tmp=new ArrayList<>();
tmp.add(nums[i]);tmp.add(nums[left]);tmp.add(nums[right]);
arr.add(tmp);
while (left<nums.length - 1 && nums[left] == nums[++left] && nums[right] == nums[--right]) {
continue;
}
}
}
while (i < nums.length - 2 && nums[i] == nums[i + 1]) {
i += 1;
}
}
return arr;
}
}
网友评论