【LeetCode】 15. 三数之和思路详解

- 日理万妓 2021-06-10 20:38 354阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处跳转）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

本身这道题也没啥思路，所以还是败给了看题解才找到答案

1.  首先想到的肯定是遍历，暴力法可以实现，大不了，就是 n3 的时间复杂度嘛，不过这样肯定不合适，所以要继续优化
2.  先排序，然后遍历绝对是少不了的，所以这一步肯定跳不过去。我们一共需要三个数，第一个数通过遍历获得，这是时间复杂度是 n。另外两个数字通过两个指针获得，一个是左指针，一个是右指针，左右两指针同时动，直到相遇为止，时间复杂度也是 n。这时的时间复杂度就变成了 n2。
3.  优化去重，这点是在代码写好之后进行的，如果一开始就能想到去重着实不是很容易。① 如果遍历到 `nums[i]` 大于0的时候，三个数字一定会大于零，因为是排过序的。 ② 左右指针在动时，判断动之后的数字和当前的数字是否相等，也就是 `nums[r-1]` 是不是等于 `nums[r]` ， `nums[l]` 是不是等于 `nums[l+1]`，循环直到找到不相同的数字为止。 ③ `nums[i]` 也要去重，如果 `nums[i]` 和之前的数字的值一样，我们就没必要再进行这一趟遍历

### 第一版代码 ###

class Solution { 
        public List<List<Integer>> threeSum(int[] nums) { 
            if(nums.length<3) return new ArrayList<>();
            Set<List<Integer>> set = new HashSet<>();
            Arrays.sort(nums);
            for (int i = 0; i <= nums.length - 3; i++) { 
                int l = i + 1;
                int r = nums.length - 1;
                while (l < r) { 
                    int temp = nums[i] + nums[l] + nums[r];
                    if (temp > 0) { 
                        r--;
                    } else if (temp < 0) { 
                        l++;
                    } else { 
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[l]);
                        list.add(nums[r]);
                        set.add(list);
                        r--;
                        l++;
                    }
                }
            }
            List<List<Integer>> lists = new ArrayList<>(set);
            return lists;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]

### 第二版代码 ###

class Solution { 
        public List<List<Integer>> threeSum(int[] nums) { 
            if (nums.length < 3) return new ArrayList<>();
            List<List<Integer>> list = new ArrayList<>();
            Arrays.sort(nums);
            for (int i = 0; i <= nums.length - 3; i++) { 
                if (nums[i] > 0) break; // 当前数字大于零，三数之和一定大于零
                if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
                int l = i + 1;
                int r = nums.length - 1;
                while (l < r) { 
                    int temp = nums[i] + nums[l] + nums[r];
                    if (temp > 0) { 
                        r--;
                    } else if (temp < 0) { 
                        l++;
                    } else { 
                        list.add(Arrays.asList(nums[i], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l + 1]) l++; // 去重
                        while (l < r && nums[r] == nums[r - 1]) r--; // 去重
                        r--;
                        l++;
                    }
                }
            }
            return list;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 2]  
可以见得优化之后时间复杂度有很大的提升

[Link 1]: https://leetcode-cn.com/problems/3sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/a44c7bf085bc49d1af718f249717c9d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/e9e254bb69b34ef2bd9c89f23bd56a67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 2]: /images/20210529/c3177bf20db04086a9d7efb1ac90c14c.png