LeetCode/15. 3Sum (Two Pointers) 20.1.28 Medium at master · BrianSong/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution: ---------------------------------------------------- Two Pointers
-------------------------------------------------------------- O(n^2) T O(1) S
class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        res, currlist = [], []
        for i in range(len(nums) - 2):                       # we let i in range(len(nums) - 2), we do not need to worry
                                                             # out of index and len(nums) == 0 or 1 or 2 problem
            if i > 0 and nums[i] == nums[i - 1]:             # i > 0 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! and nums[i] == nums[i - 1]
                                                             # Make sure the base pointer will not repeat and create duplicate triplets
                continue                                     # "continue" means finish the current loop immediately and
                                                             # jump into the next one
            left, right, currsum = i + 1, len(nums) - 1, 0
            while(left < right):
                currsum = nums[i] + nums[left] + nums[right]
                currlist = [nums[i], nums[left], nums[right]]              # Since "currlist =" insteand of "currlist.append"
                                                                           # we do not need to currlist.pop() later
                if currsum == 0:
                    res.append(currlist[:])
                    while left < right and nums[left] == nums[left + 1]:   # IMPORTANT!!!!!!!!!!!!!!
                                                                           # MUST BE left < right and nums[left] == nums[left + 1]
                                                                           # INSTEAD OF nums[left] == nums[left + 1] and left < right!!
                                                                           # because the computer will run nums[left + 1] in this,
                                                                           # and return ERROR!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                                                                           # Make sure the left pointer will not repeat
                                                                           # and create duplicate triplets
                        left += 1
                    while left < right and nums[right] == nums[right - 1]: # Make sure the right pointer will not repeat
                                                                           # and create duplicate triplets
                        right -= 1
                    left += 1                                              # Remember to  move left pointer and right pointer
                    right -= 1                                             # expecially after appending the res list
                elif currsum > 0:                                          # If currsum != 0, we do not need to worry duplicate problem
                                                                           # because it will not be append to res anyway
                    right -= 1
                else:
                    left += 1
        return res
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

'''
The correct way to remove left and right duplicate is to do:
while left < right:
      if nums[left] + nums[right] == currsum:
          res.append([nums[i], nums[left], nums[right]])
          while left < right and nums[left] == nums[left + 1]:
              left += 1
          while left < right and nums[right] == nums[right - 1]:
              right -= 1
          left += 1
          right -= 1
      elif nums[left] + nums[right] > currsum:
          right -= 1
      else:
          left += 1
Instead of:
while left < right:
      while left < right and nums[left] == nums[left + 1]:      # We cannot do the left, right duplicate remove here
          left += 1                                             # Because in this way, for example [0, 0, 0, 1]
      while left < right and nums[right] == nums[right - 1]:    # the [0, 0, 0] solution will be automatically removed
          right -= 1                                            # We can only remove left and right duplicate after we find one solution
      if nums[left] + nums[right] == currsum:                   # and try to find the next one (afraid nums[left] and nums[left + 1]
                                                                # is the same and create duplicate triplets now)
          res.append([nums[i], nums[left], nums[right]])
          left += 1
          right -= 1
      elif nums[left] + nums[right] > currsum:
          right -= 1
      else:
          left += 1
'''

Java Version
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();

        if (nums == null || nums.length < 3) {
            return res;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i ++ ){
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            } else {
                int left = i + 1;
                int right = nums.length - 1;
                while (left < right) {
                    if (nums[i] + nums[left] + nums[right] == 0) {
                        res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left += 1;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right -= 1;
                        }

                        left += 1;
                        right -= 1;
                    } else if (nums[i] + nums[left] + nums[right] > 0){
                        right -= 1;
                    } else {
                        left += 1;
                    }
                }
            }
        }

        return res;

    }
}