3Sum Ən yaxın LeetCode Həlli

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

3Sum Ən yaxın LeetCode Həlli – Tam ədəd massivi verilmişdir nums uzunluğu n və tam ədəd target, içərisində üç tam ədəd tapın nums elə ki, cəmi ən yaxın olsun target.

Qayıtmaq üç tam ədədin cəmi.

Hər bir girişin tam olaraq bir həlli olacağını güman edə bilərsiniz.

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Izahat

Qəddar qüvvə: O(N^3)

• Kobud qüvvə həlli O(N^3) olacaqdır. Biz hər bir alt çoxluğu sınaqdan keçiririk və hər iterasiyada ən yaxın məbləği yeniləyirik.

İki göstərici həlli: O(N^2)

Sual buna bənzəyir 3 cum burada bir elementi düzəldərdik və ikili axtarışdan istifadə edərək digər ikisini taparıq.

1) massivi çeşidləyin və ətrafına keçin array iki göstərici yanaşmasından istifadə etdiyimiz üçün nums.length-2 qədər.
2) iki göstərici toqquşmayana qədər döngə edin.
3) Əgər hədəf tapılarsa, artıq axtarışa ehtiyac yoxdur, ona görə də 0 işarəsi qoyun
4) Tapılan məbləğ hədəfdən böyükdürsə, massiv çeşidləndikcə, məbləğin hədəfə çatması üçün sonu azaldın.
5) Tapılan məbləğ hədəfdən azdırsa, massiv çeşidləndikcə, hədəfə çatmaq üçün məbləği artırmaq üçün başlanğıcı artırın.
6) əgər məbləğ o vaxta qədər tapılan ən yaxın məbləğdən azdırsa, ən yaxını yeniləyin.

Kodu

Ən yaxın 3sum üçün C++ kodu

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
    if(nums.size() < 3) return 0;
    int closest = nums[0]+nums[1]+nums[2];
    sort(nums.begin(), nums.end());
    for(int first = 0 ; first < nums.size()-2 ; ++first) {
        if(first > 0 && nums[first] == nums[first-1]) continue;
        int second = first+1;
        int third = nums.size()-1;            
        while(second < third) {
            int curSum = nums[first]+nums[second]+nums[third];
            if(curSum == target) return curSum;
            if(abs(target-curSum)<abs(target-closest)) {
                closest = curSum;
            }
            if(curSum > target) {
                --third;
            } else {
                ++second;
            }
        }
    }
    return closest;
}
};

Ən yaxın 3Sum üçün Java Kodu

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int result=nums[0]+nums[1]+nums[nums.length-1];
        Arrays.sort(nums);
        for (int i=0;i<nums.length-2;i++) {
            int start=i+1,end=nums.length-1;
            while(start<end) {
                int sum=nums[i]+nums[start]+nums[end];
                if(sum>target) end--;
                else start++;
                if (Math.abs(sum-target)<Math.abs(result-target)) result=sum;
            }
        }
        return result;
    }
}

Ən yaxın 3Sum üçün Python Kodu

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:        
        diff = float('inf')
        nums.sort()
        for i, num in enumerate(nums):
            lo, hi = i + 1, len(nums) - 1
            while (lo < hi):
                sum = num + nums[lo] + nums[hi]
                if abs(target - sum) < abs(diff):
                    diff = target - sum
                
                if sum < target:
                    lo += 1
                else:
                    hi -= 1
            if diff == 0:
                break
                
        return target - diff

3Sum Ən Yaxın LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (n ^ 2)

Kosmik Mürəkkəblik

O (1)