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

[ltd (Lê Trần Đạt)]

Đề bài:

• https://leetcode.com/problems/3sum

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

[Pham_Hoang]

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

[ltd (Lê Trần Đạt)]

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]

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

[Gio (Gió)]

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ó

[japananh (Trần Nhật Anh)]

Javascript

var threeSum = function(nums) {
    let len = nums.length;
    let solutionSet = [];    
    nums = nums.sort((a,b) => a - b);
    
    for (let i = 0; i < len - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        
        [j, k] = [i + 1, len - 1];
        
        while (j < k) {
            let x = nums[i] + nums[j] + nums[k];
            
            if (x === 0) {
                solutionSet.push([nums[i], nums[j], nums[k]]);
                
                while (j < k && nums[j] === nums[j + 1]) {
                    ++j;
                }
                
                while (j < k && nums[k] === nums[k - 1]) {
                    --k;
                }
                
                ++j;
                --k;
            } else if (x < 0) {
                ++j;
            } else {
                --k;
            }
        }        
    }
    
    return solutionSet;
};