C++ solution O(N^2) time


  • 1
    L
     int threeSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        const int size_n = nums.size();
        int cnt = 0;
        for (int i1 = 0; i1 < size_n; i1++) {
            int i2 = i1 + 1, i3 = size_n -1;
            while (i2 < i3) {
                int sum = nums[i1] + nums[i2] + nums[i3];
                if (sum < target) {
                    cnt += i3 - i2;
                    i2++;
                } else {
                    i3--;
                }
            }
        }
        return cnt;
    }

Log in to reply
 

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