Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Solutions:
import java.util.Arrays;
/*
0 2 3 5 6 8 10 11 14 16 18
. *
1. quick sort
2. binary search for the subarray that is smaller than the target
3. two pointers, increase left, decrease right, until found the answer
4. edge conditions
time complexity O(nlogn)
space complexity O(1) or O(N)
*/
class Solution {
public int[] twoSum(int[] nums, int target) {
//java default implementation of Arrays.sort use Dual-Pivot Quicksort
Arrays.sort(a);
//sort(nums);
int hi = rank(nums, target);
return findSums(nums, 0, hi, target);
}
public static void main(String...args) {
Solution solution = new Solution();
int[] result = solution.twoSum(solution.a, 7);
for(int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
}
private int[] a = {0, 2, 3, 5, 6, 8, 10, 11, 14, 16, 18};
private int[] findSums(int[] a, int lowBound, int highBound, int target) {
int smallIndex = lowBound;
int largerIndex = highBound;
while(a[smallIndex] + a[largerIndex] != target && smallIndex < largerIndex) {
if(a[smallIndex] + a[largerIndex] < target) smallIndex ++;
else largerIndex --;
}
int[] sums = new int[]{smallIndex, largerIndex};
return sums;
}
/*=====================the following is optional=============*/
/*
* optional
assume the array is not sorted
use merge sort or quicksort
*/
private void sort(int[] a) {
//quickSort(a);
mergeSort(a);
}
/*
* time complexity O(NlogN), worst also O(NlogN), space complexity O(N)
*/
private void mergeSort(int[] a) {
mergeSort(a, 0, a.length - 1);
}
private void mergeSort(int[] a, int lo, int hi) {
int mid = lo + (hi - lo)/2;
if(lo >= hi) return;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
private void merge(int[] a, int lo, int mid, int hi) {
int[] aux = new int[a.length];
for(int i = lo; i <= hi; i++) {
aux[i] = a[i];
}
int i = lo;
int j = mid + 1;
for(int k=lo; k <= hi; k++) {
if(i > mid) a[k] = aux[j++];
else if(j>hi) a[k] = aux[i++];
else if(a[i] >= a[j]) a[k] = a[j++];
else a[k] = a[i++];
}
}
//O(NlogN) to O(N*N) and space O(1)
private void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}
private int partition(int[] a, int lo, int hi) {
int v = a[lo];
int i = lo;
int j = hi + 1;
while(true) {
while(a[++i] <= v) if(i == hi) break;
while(a[--j] >= v) if(j == lo) break;
if(i >= j) break;
swap(a, i, j);
}
swap(a, lo, j);
return j;
}
private void quickSort(int[] a, int lo, int hi) {
if(lo >= hi) return;
int j = partition(a, lo, hi);
quickSort(a, lo, j - 1);
quickSort(a, j + 1, hi);
}
private void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
/*optional*/
private int rank(int[] a, int target) {
int lo = 0;
int hi = a.length - 1;
while(lo <= hi) {
int mid = lo + (hi - lo)/2;
if(target < a[mid]) hi = mid - 1;
if(target > a[mid]) lo = mid + 1;
else return mid;
}
return lo;
}
}
