Sharing O(n^2) Solution in C++ (Should be easy to understand)


  • 0
    Y
    class Solution {
    public:
        int threeSumSmaller(vector<int>& nums, int target) {
            int ans = 0;
            if(nums.size() == 0)
                return ans;
            //O(nlogn)
            sort(nums.begin(), nums.end());
            int sta = 0, nd = nums.size() - 1;
            //O(n^2) while loop
            while(nd >= 2){
                sta = 0;
                int sum = nums[sta] + nums[nd];
                int sta_nd = nd - 1;
                //O(n) while loop
                while(sta < sta_nd){
                    sum = nums[sta] + nums[nd];
                    while(sum + nums[sta_nd] >= target && sta < sta_nd) 
                        -- sta_nd;
                    ans += (sta_nd - sta);
                    ++ sta;
                }
                -- nd;
            }
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.