3 sum smaller C++ solution n^2logn


  • 0
    A
    class Solution {
    public:
        int search_less_than_target(vector<int> &nums, int target, int beg) {
          int orig = beg;
          int end = nums.size()-1;
          while (beg <= end) {
              int mid = beg + (end-beg)/2;
              if (nums[mid] < target) {
                  beg = mid+1;
              }
              else {
                  end = mid-1;
              }
          }
          end = end > nums.size()-1 ? nums.size() - 1 : end;
          return end-orig+1;
        }
        
        int threeSumSmaller(vector<int>& nums, int target) {
            if (nums.size() < 2) return 0;
            sort(nums.begin(), nums.end());
            int ans = 0;
            for (size_t i = 0; i  < nums.size(); ++i) {
                for (size_t j = i+1; j < nums.size(); ++j) {
                    auto diff = target - (nums[i] + nums[j]);
                    ans  += search_less_than_target(nums, diff, j+1);
                }
            }
            return ans;
        }
    };

Log in to reply
 

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