LeetCode15. 3Sum

1、题目链接

https://leetcode.com/problems/3sum/

2、解题思路

这道题的意思是说给你一个整数的数组，让你从中找出3个数相加等于0的所有情况，题目意思并不难理解，我们来分析一下，如果相加为0的话，那么就有以下几种情况：

1、三个数都为0

2、其中一个为0，另外两个一正一负且相等

3、两个正数一个负数（两个负数一个正数）且正数的和等于负数

如果我们固定其中某一个的值，然后动态的去找另外两个数的值，是不是也算一种方法呢？于是乎就有了如下代码；首先将数组进行遍历，这么做是为了排除掉一些可能，然后我们将数组的0~(len-1)个数依次作为固定的数，然后通过从负数这边最小和正数那边最大来从左右两边进行收缩遍历，直到找到符合条件的三个数：

3、代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (null != nums && nums.length >= 3) {
            Arrays.sort(nums);
            int len = nums.length;
            // 最大的数必须大于0，且最小的数必须都小于0
            if (nums[0] <= 0 && nums[len - 1] >= 0) {
                // 随便选中一个数（这里从最小的开始），然后从这个数的右边以及数组的最右边开始往中间遍历
                for (int i = 0; i < len; i++) {
                    if (nums[i] > 0) {
                        break;
                    }
                    //这一步为了去除重复操作，因为我们在i-1的时候已经搜索过一次了，再搜索一边已经没有什么意义
                    if (i > 0 && nums[i] == nums[i - 1]) {
                        continue;
                    }
                    int m = i + 1;
                    int n = len - 1;
                    //开始从左右两边往中间遍历
                    while (m < n) {
                        if (n < len - 1 && nums[n] == nums[n + 1] || nums[i] + nums[m] + nums[n] > 0) {
                            // 当结果大于0时，那么我们肯定希望结果更小，这时候将最右侧的下标向左移动
                            n--;
                        } else if (m > i + 1 && nums[m] == nums[m - 1] || nums[i] + nums[m] + nums[n] < 0) {
                            // 当结果小于0时，那么我们肯定希望结果更大，这时候将最左侧的下标向右移动
                            m++;
                        } else {
                            List<Integer> itemList = new ArrayList<>();
                            itemList.add(nums[i]);
                            itemList.add(nums[m]);
                            itemList.add(nums[n]);
                            resultList.add(itemList);
                            // 符合条件，需要将左右两边的下标都移动
                            m++;
                            n--;
                        }
                    }
                }
            }
        }
        return resultList;
    }
}

4、结果

WX20190807-214229@2x.png