iT邦幫忙

2021 iThome 鐵人賽

DAY 4
0
自我挑戰組

開學之前....系列 第 4

Day4- 15. 3Sum

今日題目:15. 3Sum(Medium)

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:
Input: nums = []
Output: []

Example 3:
Input: nums = [0]
Output: []

Constraints:

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

思路

(待補)(我已經太疲憊)

My solution:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)

        if n == 0 or n==2: return []
        
        ans = []
        nums.sort()
        print(nums)
        i = 0
        for i in range(n-2):
            if nums[i] == nums[i-1] and i>0:
                continue
            j = i+1
            k = n-1
            temp = nums[j]+nums[k]
           
            while k>j:
                temp = nums[j] + nums[k]

                if temp > -nums[i]:
                    k-=1
                elif temp<-nums[i]:
                    j+=1
                else:
                    while nums[k] == nums[k - 1] and k > j:
                        k-=1
                    while nums[j] == nums[j + 1] and k > j:
                        j += 1
                    ans.append([nums[i],nums[j],nums[k]])
                    j+=1
                    k-=1
        return(ans)

Result

https://ithelp.ithome.com.tw/upload/images/20210919/20140843C1561VLqEH.png

題目不難,但是有很多details必須注意
如不注意
就會與我一樣,耗費了一整個下午:))


上一篇
Day3-LeetCode Medium+Easy
下一篇
Day5-75. Sort Colors
系列文
開學之前....20

尚未有邦友留言

立即登入留言