Is This Solution O(n2) or O(n3)


  • 0
    C

    I suspect it is O(n3) but not so sure. Could someone give me any suggestion?

    Thanks in advance.

    public class Solution {
        public int threeSumSmaller(int[] nums, int target) {
            if (nums == null || nums.length == 0) return 0;
            int result = 0, fix = 0, start = 1, end = nums.length - 1;
            Arrays.sort(nums);
            while (fix < nums.length - 2) {
                while (start < end) {
                    while (start < end && nums[fix] + nums[start] + nums[end] < target) {
                        result++;
                        start++;
                    } 
                    end--;
                    start = fix + 1;
                }
                fix++;
                start = fix + 1;
                end = nums.length - 1;
            }
            return result;
        }
    }

Log in to reply
 

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