# Share my java AC solution.

• Without HashMap, just have two pointers, A points to index 0, B points to index len - 1, shrink the scope based on the value and target comparison.

``````public int[] twoSum(int[] num, int target) {
int[] indice = new int[2];
if (num == null || num.length < 2) return indice;
int left = 0, right = num.length - 1;
while (left < right) {
int v = num[left] + num[right];
if (v == target) {
indice[0] = left + 1;
indice[1] = right + 1;
break;
} else if (v > target) {
right --;
} else {
left ++;
}
}
return indice;
}``````

• This post is deleted!

• The code is clean and elegant, but I would change one line:

``````long v = num[left] + num[right];
``````

in case of the integer overflow.

• great solution. i know it works, but am struggling to understand why; feel like magic. can you explain a little bit.

• Great solution, but could you explain a bit how it's utilizing its already SORTED attribute?

• Since the array is sorted, we can leverage it by using binary search which is O(logn) instead of a HashMap solution which is O(n) . So the code is simple and self explanatory for most of the part. It is noting but Binary search as we already have a sorted array

• Can I ask why the big O here is O(log n)? Actually, what happen here is not binary search. It just use two pointers and worst case could be O(n).

• I think its still O(n) because the number of element you have to check is still proportional to the length of given int array.

• what's the time complexity of this two pointers solution? O(logN)?

• nicer and shorter!

``````public int[] twoSum(int[] numbers, int target) {
int start = 0, end = numbers.length - 1;
while(start < end){
if(numbers[start] + numbers[end] == target) break;
if(numbers[start] + numbers[end] < target) start++;
else end--;
}
return new int[]{start + 1, end + 1};
}``````

• O(n), no binary reducing search place here

• shorter

``````public int[] twoSum(int[] numbers, int target) {
for (int i = 0, n = numbers.length; i < n - 1; i++) {
int j = Arrays.binarySearch(numbers, i + 1, n, target - numbers[i]);
if (j > 0) return new int[]{i + 1, j + 1};
}
return null;
}``````

• @ofLucas
this is n(logn) right?:clap:

• Seems not a O(logn) solution. The key point of binary search which can bring you O(logN) is divide the space by two. Which means something like right = mid or left = mid. But the code here is simply incrementing and decrementing. I would say it's a O(n) solution.

• Could someone explain why the indice[0] is left + 1 instead of just left? If we found the correct sum at index of left and right why do we increment each by 1?

• @vimukthi But the run time of your program is 2ms, which is slower. I don't know why, can anybody who explain?

• @aoben10 this is required by this problem. You can read it from the description. The index starts from 1, instead of 0.

• This post is deleted!

• @Harrywithcode Time Limit Exceeded might be occurred when n is a big data and the target i, j is in the center of the array.
For example,
[0,0,0,0,...,0,2,3,9,9,...,9] target sum is 5

• I logged in just to upvote your solution. Good job PO!

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