当前位置：首页 > article >正文

【优选算法】三数之和

article 2025/1/6 2:57:47

链接：15. 三数之和 - 力扣（LeetCode）

算法原理：

方法：排序+双指针+去重

1.排序

2.固定一个数 a（a <= 0）

3.在该数后面的区间内，利用“双指针算法”快速找到两个的和等于 -a 即可

4.去重

找到一种结果之后，left 和 right 指针要跳过重复元素

当使用完一次双指针算法之后，i 也需要跳过重复元素

避免越界

5.不漏

找到一种结果之后，不要“停”，缩小区间，继续寻找

代码编写：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        //1.排序
        Arrays.sort(nums);
        //2.利用双指针解决问题
        int n = nums.length;
        for(int i = 0; i < n;){
            if(nums[i] > 0){
                break;
            }
            int left = i + 1, right = n - 1, target = -nums[i];
            while(left < right){
                int sum = nums[left] + nums[right];
                if(sum > target){
                    right--;
                }else if(sum < target){
                    left++;
                }else{
                    //nums[i] nums[left] nums[right]
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
                    left++;
                    right--;//缩小区间继续寻找
                    //去重
                    while(left < right && nums[left] == nums[left-1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right+1]){
                        right--;
                    }
                }
            }
            //去重：i
            i++;
            while(i < n && nums[i] == nums[i-1]){
                i++;
            }
        }
        return ret;
    }
}

复杂度分析：