3sum 不sort

2018-02-10  本文已影响0人  greatseniorsde
class Solution {
  
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3){
            return res;
        }
        Set<Integer> firstNum = new HashSet<>();
        //[-1, 0, 1, 2, -1, -4]
        //firstNum:-1
        //i = 1 sum = 0
        //secondNum:
        //thirdNum:
        //j = 2
        //res:[-1,1,0] [-1, -1, 2]
        for (int i = 0; i < nums.length; i++){
            if (firstNum.contains(nums[i])){
                continue;
            }
            int sum = -nums[i];
            Set<Integer> secondNum = new HashSet<>();
            Set<Integer> thirdNum = new HashSet<>();
            for (int j = i + 1; j < nums.length; j++){
                if (!firstNum.contains(nums[j]) && !thirdNum.contains(nums[j])){
                    if (secondNum.contains(sum - nums[j])){
                        res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], sum - nums[j])));
                        thirdNum.add(nums[j]);
                    } else {
                        secondNum.add(nums[j]);
                    }
                }
            }
            firstNum.add(nums[i]);
        }
        return res;
    }
       
}
上一篇下一篇

猜你喜欢

热点阅读