Most straightforward c++ solution


  • -2
    J

    sort first and brutal search.

    class Solution {
    public:
        int threeSumSmaller(vector<int>& nums, int target) {
            if(nums.size()<3)return 0;
            sort(nums.begin(),nums.end());
            int res=0;
            for(int i=0;i<nums.size()-2;++i){
                if(nums[i]+nums[i+1]+nums[i+2]>=target)break;
                for(int j=i+1;j<nums.size()-1;++j){
                    if(nums[i]+nums[j]+nums[j+1]>=target)break;
                    for(int k=j+1;k<nums.size();++k){
                        if(nums[i]+nums[j]+nums[k]>=target){
                            break;
                        }else{
                            res++;
                        }
                    }
                }
            }
            return res;
        }
    };

  • 2

    I'd say this is more straightforward :-)

    int threeSumSmaller(vector<int>& nums, int target) {
        int count = 0;
        for (int k=2; k<nums.size(); ++k)
            for (int j=1; j<k; ++j)
                for (int i=0; i<j; ++i)
                    count += nums[i] + nums[j] + nums[k] < target;
        return count;
    }

  • 0
    M

    As my understanding, we can not sort the array since we need to keep the i < j < k.
    Is that right?


  • 0
    J

    I do not think so. After sorting the array, the original indexes of the three distinct number still satisfy i<j<k


  • 0

    That really just means that the three indexes need to be distinct and that you must not count each triplet six times (as each triplet has 3! permutations). Reordering the numbers doesn't change the result.


  • 0
    J

    Yea, you are right.


  • 0
    S

    I think this problem is miswritten.As it states,we can't sort!!!


Log in to reply
 

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