美文网首页每日打卡
2021-11-25 006,007

2021-11-25 006,007

作者: 16孙一凡通工 | 来源:发表于2021-11-25 20:26 被阅读0次

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;
    }
}

相关文章

网友评论

    本文标题:2021-11-25 006,007

    本文链接:https://www.haomeiwen.com/subject/zwsztrtx.html