[King Back] Summary of 2 similar implementations with Comments


  • 0

    I have 2 months to prepare my Google interview, so I come back to practice my basic grasp of the code force!

    Here are 2 simple implementations may help you get the ideas!

    First solution,

    /** solution -1- **/
    class Solution {
    	int threeSumSmaller(vector<int>& nums, int target) {
    		sort(nums.begin(), nums.end());
    		const int n = nums.size();
    		int count = 0;
    		/** accumlate the triplet end with k **/
    		for (int k = 2; k < n; ++k) {
    			int i = 0, j = k - 1;
    			/** in fact this is 2-pointer problem find the target value = (target - nums[k]) **/
    			while (i < j) {
    				if (nums[i] + nums[j] + nums[k] >= target) {
    					--j;
    				} else {
    					/** the triplet contains nums[i] **/
    					count += j - i;
    					++i;
    				}
    			}
    		}
    		return count;
    	}
    }
    

    Second solution,
    This solution is more easy to understand as we refer the idea of the 2 pointers. We just loop to find all the possible combinations,
    to avoid missing some cases, so we should clarify that we loop all the possible start index i, then loop all the possible left options,
    then loop all the possible right index option, to accelerate, we just need to find the first right element satisfy the condition, then
    we get "count + = right - left"

       /** solution -2- **/
        class Solution {
        	int threeSumSmaller(vector<int>& nums, int target) {
        		sort(nums.begin(), nums.end());
        		const int n = nums.size();
        		int count = 0;
        		for (int i = 0; i < n - 2; i++) {
        			int left = i + 1, right = len - 1;
        			while (left < right) {
        				if (nums[i] + nums[left] + nums[right] < target) {
        					count += right - left;
        					left ++;
        				} else {
        					right --;
        				}
        			}
        		}
        		return count;
        	}
        }

  • 0
    N

    I think your 2 solutions are same.
    btw, 'len' should be n in "int left = i + 1, right = len - 1;", solution #2.


Log in to reply
 

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