21.03.09 LeetCode15. 三数之和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

 

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [0]
输出：0
示例 4：

输入：nums = [-1]
输出：-1
示例 5：

输入：nums = [-100000]
输出：-100000。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //先排序，再从0开始对
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int len = nums.length;
        if(nums==null || len<3)
            return ans;
        Arrays.sort(nums);
        //这里的终止条件，可以写len也可以写len-2，写len-2会更加减少执行用时
        //因为少了两次循环，在所有测试用例加起来就少了很多次
        for(int i = 0;i<len-2;i++)
        {
            if(nums[i]>0)
                break;
            if(i>0 && nums[i] == nums[i-1])
                continue;
            int L = i+1;
            int R = len-1;
            while(L<R)
            {
                int sum = nums[i]+nums[L]+nums[R];
                if(sum==0)
                {
                    List<Integer> t = new ArrayList<>();
                    t.add(nums[i]);t.add(nums[L]);t.add(nums[R]);
                    ans.add(t);
                    while(L<R && nums[L] == nums[L+1])
                        L++;
                    while(L<R && nums[R] == nums[R-1])
                        R--;
                    L++;R--;
                }
                else if(sum<0)
                    L++;
                else if(sum>0)
                    R--;
            }
        }
        return ans;
       
    }
}