Java 2ms solution - no hashmaps, 2 simple loops


  • 6
    E
    public class Solution {
        public int[] twoSum(int[] nums, int target) {
            // Since x1 + x2 = target, we can in one loop 
            // mark both x1 and x2 in some additional array where we'll keep indices
            // Though to build that array we'd need another loop
            
            int min=0, max=0;
            // first loop to find max and min integers
            for (int i = 0;i<nums.length;i++)
            {
                if (i==0)
                {min = nums[i];max = min;}
                else
                {
                    if (nums[i] < min)
                        min = nums[i];
                    if (nums[i] > max)
                        max = nums[i];
                }
            }
            // valid range for input integers relative to target
            int sMin = Math.max(min,target - max);
            int sMax = Math.min(max,target - min);
            
            // array to keep indices of valid input integers
            // initialize with -1
            int size = 1 + sMax - sMin;
            int[] arr = new int[size];
            for (int i = 0; i< arr.length;i++)
                arr[i] = -1;
            
            // second loop
            int offset = -sMin;
            for (int i = 0;i<nums.length;i++)
            {
                // Skip if integer is not from a valid range
                if (nums[i] > sMax || nums[i] < sMin)
                    continue;
                // if found valid X1 and corresponding element of indices array is still -1
                // then mark its pair X2 = target - X1 in indices array
                if (arr[nums[i] + offset] == -1)
                    arr[target-nums[i] + offset] = i;
                else
                    return new int[]{arr[nums[i] + offset],i};
            }
           
            return new int[]{0,0};
            
        }
    }

  • 0
    B

    it can be more simple as the code


  • 2
    F

    In worst case:
    if min is int(0.25 * INT_MAX), max is int(0.75 * INT_MAX) and target is INT_MAX,
    then sMin is int(0.25 * INT_MAX) and sMax is int(0.75 * INT_MAX) more or less.
    size will be int(0.5 * INT_MAX), that is not good.


  • 1

    your answer is really awesome, it runs within less time. However, I have spent 3 hours to read your code but I am still confused. If possible, please explain more about these three lines.
    if (arr[nums[i] + offset] == -1)
    arr[target-nums[i] + offset] = i;
    else
    return new int[]{arr[nums[i] + offset],i};
    }


Log in to reply
 

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