# O(n^2) Java solution with bound optimization

• The main idea is get target number in a sorted array

1. sort the input array
2. set left index to be 0, right index to be nums.length -1
3. calculate the target number(0-nums[left]-nums[right])
4. search the target number in sorted array

The AC code

``````    public List<List<Integer>> threeSum(int[] nums) {

Arrays.sort(nums);

List<List<Integer>> result = new ArrayList<>();

if (nums == null || nums.length < 3) {
return result;
}

for(int left = 0; left< nums.length && nums[left] <= 0; ) { //left loop to first 0
boolean flag = true;
for(int right = nums.length - 1; flag && right> 0 && nums[right] >= 0;) {//right loop to last 0
int curr = 0 - nums[left] - nums[right]; // target number
if (right > 0 && nums[right - 1] < curr) { //no need to search, break the right loop
flag = false;
continue;
}
int k = 0; // target number index
if(curr< 0) { //search from left to right
k = left;
while (++k < right && nums[k] < curr) ;

} else { //search target from right to left
k = right;
while (--k > left && nums[k] > curr) ;
}
if(k>left && k < right && nums[k] == curr) { //bingo
List<Integer> added = new ArrayList<>();
}
int iRight = right;
while(--right >= 0 && nums[right] == nums[iRight]) ; //skip duplicated numbers
}
int index = left;
if(nums[left] >= 0) break; //break when we met first 0, time optimization
while(++left < nums.length && nums[left] == nums[index]) ; //skip duplicated numbers
}
return result;
}
``````

• I just thought maybe i can use binary-search to get the target number, and it works

``````    public List<List<Integer>> threeSum(int[] nums) {

Arrays.sort(nums);

List<List<Integer>> result = new ArrayList<>();

if (nums == null || nums.length < 3) {
return result;
}

for(int left = 0; left< nums.length && nums[left] <= 0; ) { //left loop to first 0
boolean flag = true;
for(int right = nums.length - 1; flag && right> 0 && nums[right] >= 0;) {//right loop to first 0
int curr = 0 - nums[left] - nums[right]; // target number
if (right > 0 && nums[right - 1] < curr) { //no need to search, break the right loop
flag = false;
continue;
}
int k = biSearch(nums, curr, left+1, right-1); //biSearch target number index
if(k>0 && nums[k] == curr) { //bingo
List<Integer> added = new ArrayList<>();
}
int iRight = right;
while(--right >= 0 && nums[right] == nums[iRight]) ; //skip duplicated numbers
}
int index = left;
if(nums[left] >= 0) break; //break when we met first 0, time optimization
while(++left < nums.length && nums[left] == nums[index]) ; //skip duplicated numbers
}
return result;
}

private int biSearch(int[] array, int target, int left, int right) {

while(left <= right) {
int mid = (left + right) / 2;
if(array[mid] > target) {
right = mid - 1;
} else if(array[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
``````

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