Giải bài 15 3sum O(N^2)

interview
leetcode

(Lê Trần Đạt) #1

Đề bài:

Bài giải:

Code Python

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        n = len(nums)
        ans = []
        for i in xrange(n - 2):
            if i and nums[i] == nums[i - 1]:
                continue
            j = i + 1
            k = n - 1
            while j < k:
                a, b, c = nums[i], nums[j], nums[k]
                x = a + b + c
                if x == 0:
                    ans.append([a, b, c])
                    while j < k and nums[j] == nums[j + 1]: j += 1
                    while j < k and nums[k] == nums[k - 1]: k -= 1
                    j, k = j + 1, k - 1
                elif x < 0:
                    j += 1
                else:
                    k -= 1
        return ans

Nhờ các bạn giải với ngôn ngữ khác


Topic tổng hợp các video chia sẻ về interview của ltd
(Pham Hoang) #2

Bài này có cách nào chạy nhanh hơn O(n^2) ko anh nhỉ :thinking:?


(Lê Trần Đạt) #3

Tạm thời chưa nghĩ ra. Lần submit nhanh nhất của anh (với cái code này) là thế này rồi. Beats 98.51%.


(doanguyen) #4

def threeSum(self, nums), what a name!


(Gió) #5

Cái này đếm số lượng thì có thể làm trong O(nlogn) còn liệt kê thì hơi khó :slight_smile:


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?