图解双指针解决三数之和、最接近的三数之和

双指针解决三数之和

模板代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * $15、$16的模板代码
 */
class Solution {
    public List<List<Integer>> threeSum2(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();

        //1.排序
        Arrays.sort(nums);

        //2.枚举i
        for (int i = 0; i < len; i++) {
            //需要和上一次枚举的数不同
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            
            //3.确定l，r
            //l的初始值是i的下一个
            int l = i+1;
            //r的初始值是数组的最右端
            int r = len-1;
            int target = ;
            
            //5.当l<r时
            while (l < r) {
                int sum = 左右指针对应值或者其他相关;
//                //需要和上一次枚举的数不同
//                if (l > i+1 && nums[l] == nums[l-1]) {
//                    l++;
//                    continue;
//                }
                //5.1通过与target的比较，来调整l与r的位置
                if (sum < target) {
//                    //移动到下一个不相同的元素
//                    while (l+1 < r && nums[l] == nums[l+1]) {
//                        l++;
//                    }
                    l++;
                } else if (sum > target) {
//                    //移动到下一个不相同的元素
//                    while (r-1 > l && nums[r] == nums[r-1]) {
//                        r--;
//                    }
                    r--;
                } else {
                    //结果处理
                }
            }
        }
        return res;
    }
}

三数之和

OJ链接

import java.util.*;

public class $15 {
    //左右指针
    public List<List<Integer>> threeSum2(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();

        //排序
        Arrays.sort(nums);

        //枚举a
        for (int i = 0; i < len; i++) {
            //需要和上一次枚举的数不同
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            //b的初始值是a的下一个
            int l = i+1;
            //c的初始值是数组的最右端
            int r = len-1;
            int target = -nums[i];
            while (l < r) {
                //需要和上一次枚举的数不同
                if (l > i+1 && nums[l] == nums[l-1]) {
                    l++;
                    continue;
                }
                if (nums[l] + nums[r] < target) {
//                    while (l+1 < r && nums[l] == nums[l+1]) {
//                        l++;
//                    }
                    l++;
                } else if (nums[l] + nums[r] > target) {
                    r--;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[l]);
                    list.add(nums[r]);
                    res.add(list);
//                    while (l+1 < r && nums[l] == nums[l+1]) {
//                        l++;
//                    }
                    l++;
                }
            }
        }
        return res;
    }
}

最接近的三数之和

OJ链接

import java.util.Arrays;

public class $16 {
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;

        //排序
        Arrays.sort(nums);

        int best = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            //需要和上一次枚举的数不同
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            int l = i+1;
            int r = len-1;

            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];

                //更新差值的的绝对值来更新答案
                if (Math.abs(sum-target) < Math.abs(best-target)) {
                    best = sum;
                }

                if (sum < target) {
                    //移动到下一个不相同的元素
                    while (l+1 < r && nums[l] == nums[l+1]) {
                        l++;
                    }
                    l++;
                } else if (sum > target) {
                    //移动到下一个不相同的元素
                    while (r-1 > l && nums[r] == nums[r-1]) {
                        r--;
                    }
                    r--;
                } else {
                    return target;
                }
            }
        }
        return best;
    }
}