Java 2ms solution - no hashmaps, 2 simple loops

• ``````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};

}
}``````

• it can be more simple as the code

• 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.

• 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};
}

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