【leetcode19】三数之和==有点难还没看懂❗==

原题链接

方法一：双指针法
这道题目使用双指针法 要比哈希法高效一些

解题思路链接：
https://www.programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E6%80%9D%E8%B7%AF

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(nums);
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for(int i=0;i<nums.length;i++){
        // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
        if(nums[i]>0) return result;
        if(i>0&&nums[i]==nums[i-1]) continue;// 去重a
        int left=i+1;
        int right=nums.length-1;
        while(right>left){
            int sum=nums[i]+nums[left]+nums[right];
            if(sum>0){
                right--;
            }else if(sum<0){
                left++;
            }else{
                result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                while(right>left&&nums[right]==nums[right-1])right--;
                while(right>left&&nums[left]==nums[left+1])left++;

                right--;
                left++;
             }
            }
        }
        return result;
    }
}

方式二：使用哈希集合

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);

for (int i = 0; i < nums.length; i++) {
// 如果第一个元素大于零，不可能凑成三元组
if (nums[i] > 0) {
return result;
}
// 三元组元素a去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}

HashSet<Integer> set = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
// 三元组元素b去重
if (j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) {
continue;
}

int c = -nums[i] - nums[j];
if (set.contains(c)) {
result.add(Arrays.asList(nums[i], nums[j], c));
set.remove(c); // 三元组元素c去重
} else {
set.add(nums[j]);
}
}
}
return result;
    }
}

原文地址：https://blog.csdn.net/weixin_45780075/article/details/145157322

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！