Simple java solution(should be O(n^2)?)


  • 0
    C
    public class Solution {
        public int threeSumSmaller(int[] nums, int target) {
            if(nums.length==3) return (Arrays.stream(nums).sum()) < target? 1:0;
            Arrays.sort(nums);
            int head, lend, rend, count=0;
            for(head=0;head<nums.length-2;head++){
                lend = head+1;
                rend = nums.length-1;
                while(lend < rend){
                    int needed = target - nums[lend] - nums[head] - 1;
                    if(nums[rend] <= needed){
                        count += rend - lend;
                        lend++;
                    }else{
                        rend--;
                    }
                }
            }
            return count;
        }
    }

  • 1
    V

    I think it is O(n^2), since when head is set, the movement of lend and rend is monotone.


Log in to reply
 

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