15.3Sum.md

15. 3Sum

Difficulty: Medium

URL

https://leetcode.com/problems/3sum/https://leetcode.com/problems/word-ladder

Solution

Approach 1: Two Pointers

This is the most intuitive approach coming to my mind. To index three numbers, we keep track of each number with a pointer, sorting from left to right. First we sort the input array, to make sure that the final output is consisten with the required format.The first round of the iteration keeps track of the index for the first number with a pointer called index . Then we maintain two pointers, left and right. The initial values are left = index+1, right = arr_size-1.Then we calcualte the sum and compare it with 0, if the sum is less than 0, move the left pointer to the right. If the sum is greater than 0, then move the right pointer to the left. We also need to skip several steps just to eliminate redundancy.

The code is shown below:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        arr_size = len(nums)
        res = []
        for index in range(arr_size-2):
            if index >= 1 and nums[index] == nums[index - 1]:
                continue
            # initial value for pointers
            left_ptr = index + 1
            right_ptr = arr_size-1
            num1 = nums[index]
            while left_ptr < right_ptr:
                num2 = nums[left_ptr]
                num3 = nums[right_ptr]
                sum_temp = num1 + num2 + num3
                if sum_temp < 0:
                    # move the left pointer to the right to increase the sum
                    left_ptr += 1
                elif sum_temp > 0:
                    # move the right pointer to the left to decrease the sum
                    right_ptr -= 1
                # remove duplicates
                else:
                    while right_ptr > left_ptr and nums[right_ptr] == nums[right_ptr-1]:
                        right_ptr -= 1
                    while right_ptr > left_ptr and nums[left_ptr] == nums[left_ptr+1]:
                        left_ptr += 1
                    res.append([num1, num2, num3])
                    # initialize a new round
                    left_ptr += 1
                    right_ptr -= 1

        return res