长大后想做什么？做回小孩！

0%

LeetCode——最接近的三数之和

发表于 更新于 分类于 Valine：
本文字数： 503

NO.16 最接近的三数之和 中等

QHphH1.png

思路一：暴力破解法

用list保存所有的三数之和的情况，然后找出最接近target的数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int threeSumClosest(int[] nums, int target) {
        int len=nums.length;
    	if (nums==null||len<3)throw new IllegalArgumentException("error of argument!");
//        用list保存所有的三数之和
        List<Integer> list=new ArrayList<>();
        for (int i=0;i<len;i++){
            for (int j=i+1;j<len;j++){
                for (int k=j+1;k<len;k++){
                    list.add(nums[i]+nums[j]+nums[k]);
                }
            }
        }
//        遍历list找出最接近target的数
        int ans=list.get(0);
        for (Integer i : list) {
            if (Math.abs(target-ans)>Math.abs(target-i))
                    ans=i;
        }
        return ans;
    }

时间复杂度：O(n^3)

思路二：双指针法

和第15题的双指针法思路类似，本题免去了去重的操作。1. 先对数组排序，时间复杂度O(nlogn)。2. 依次遍历每个元素nums[i]。3. 然后用前后指针L=i+1和R=nums.length-1分别指向nums[i]后面部分的开头nums[L]和结尾nums[R]。4. 得到sum=nums[i]+nums[L]+nums[R]，如果sum更接近target，就更新ans。5. 如果sum==target，就已经找到最接近target的三数之和，返回sum；如果sum>target，说明需要小一点的数来组合，即R–；如果sum<target，说明需要大一点的数来组合，即L++。6. 如果没有得到sum==target，那么每次双指针都需要遍历所有”后面所有元素”，即while(L<R)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int threeSumClosest(int[] nums, int target) {
        int len= nums.length,ans=nums[0]+nums[1]+nums[2];
        if (nums==null||len<3)throw new IllegalArgumentException("error of argument!");
//        对数组排序
        Arrays.sort(nums);
//        依次遍历每个元素nums[i]
        for (int i=0;i<len;i++){
//            然后用前后指针L和R分别指向nums[i]后面部分的开头和结尾
            int L=i+1;
            int R=len-1;
            while (L<R){
                int sum=nums[i]+nums[L]+nums[R];
                if (Math.abs(target-ans)>Math.abs(target-sum)){
                    ans=sum;
                }
                if (sum==target){//如果sum==target，那就已经找到最接近target的三数之和
                    return ans;
                }else if (sum<target){//如果sum<target，说明需要大一点的数来组合，即L++
                    L++;
                }else if (sum>target){//如果sum<target，说明需要小一点的数来组合，即R--；
                    R--;
                }
            }
        }
        return ans;
    }

时间复杂度：O(n^2) 整个遍历过程，固定值为 n 次，双指针为 n 次。

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github