LeetCode 每日一题

三数之和

image.png

思路

双指针
对于原始数组可以通过排序之后,来优化处理元素相同的情况。
在遍历元素的同时相当于已经有了索引指针,需要在内部在再维护一对双指针来进行头元素,对应的存在满足条件的元素对。

class Solution{
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> ans  = new ArrayList<>();
        Arrays.sort(nums);  // 先排序
        int len = nums.length;
        if(len<3) return ans; //  边界条件,当元素不满足3个时直接处理
        for(int i=0;i<len;i++){  // 此处索引 i 已经维护了一个指针,那么对于剩下的两个元素 ,在遍历的内部需要维护下。
            if(nums[i]>0) return ans; //排序后的首元素都大于3了,那么肯定不存在满足的情况,直接处理
            if(i>0 && nums[i-1] == nums[i])  continue; //首元素相同时的处理逻辑
            int left=i+1,right=len-1;
            // 内部while 循环结合排序好的输入数组,通过双指针来进行当首元素确定后的遍历情况
            while(left<right){
                int sum = nums[i]+nums[left]+nums[right]; //判断条件
                if(sum==0){
                    ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left < right && nums[left] == nums[left+1]) left++;
                    while(left < right && nums[right-1] == nums[right]) right--;
                    left++;
                    right--;
                }else if(sum<0){
                    left++;
                }else right--;
            }
        }
        return ans;
    }
}

关于作者

Kirago
扯淡第一名
获得点赞
文章被阅读