leetcode 01両数の和

package LeetCode;
import java.util.HashMap;
import java.util.Map;

/**
 * @author jinhuajian
 * @data 2018 12 19 ---  10:53:15
 * @blog https://me.csdn.net/qq_37119939          target input :int[] arr, int
 *       target; output : int [i,j]   arr[i] + arr[j] = target , i != j;
 */
class Solution {
	//      O(n^2)，    O(1)，
	//    ，  i,       i   j， arr[i] + arr[j] = target ，  {i,j};       O(N)
	//         i ，     O(N)
	public int[] twoSum_1(int[] nums, int target) {
		if (nums == null && nums.length < 1) {
			return nums;
		}
		for (int i = 0; i != nums.length; i++) {
			for (int j = i + 1; j != nums.length; j++) {
				if (nums[i] + nums[j] == target) {
					return new int[] { i, j };
				}
			}
		}
		throw new IllegalArgumentException("No two sum solution!");
	}

	//  hashMap       O(N) key： arr[i], value： key   i;
	//               hashMap，     ，   i ，  target-arr[i]     HashMap 
	//        map.containsKey();    ，     key    value,          j,   {i,j}
	//   Java             ，          ，     ，throw new RuntimeException("No correct
	// solution! "):
	public int[] twoSum_2(int[] nums, int target) {
		if (nums == null && nums.length < 1) {
			return nums;
		}
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i != nums.length; i++) {
			map.put(nums[i], i);
		}
		for (int i = 0; i != nums.length; i++) {
			int cha = target - nums[i];
			// map.constainsKey(key);hashMap   key      
			if (map.containsKey(cha) && map.get(cha) != i) {
				return new int[] { i, map.get(cha) };
			}
		}

		throw new RuntimeException("No two sum solution!");
	}

	//             ，   ，                 
	public int[] twoSum_3(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i != nums.length; i++) {
			int cha = target - nums[i];
			if (map.containsKey(cha)) {
				return new int[] { map.get(cha), i };
			}
			map.put(nums[i], i);
		}
		throw new RuntimeException("No two sum solution!");
	}

	//      ：   ，     ，              ，        ，          
	public int[] twoSum(int[] nums, int target) {
		if (nums == null && nums.length < 1) {
			return nums;
		}
		sortChoose(nums);
		int l = 0;
		int r = nums.length - 1;
		while (l < r) {
			if (nums[l] + nums[r] < target) {
				l++;
			} else if (nums[l] + nums[r] > target) {
				r--;
			} else {
				break;
			}
		}
		return new int[] { nums[l], nums[r] };

	}

	//     O(n^2)
	public void sortArr(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			for (int j = arr.length - 1; j != i; j--) {
				if (arr[j] < arr[j - 1]) {
					swap(arr, j, j - 1);
				}
			}
		}
	}

	//     O(n^2)
	public void sortChoose(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			int min = i;//   [i,n-1]        j
			for (int j = i + 1; j != arr.length; j++) {
				if (arr[min] > arr[j]) {
					min = j;
				}
			}
			swap(arr, min, i);//  [i,n-1]         i  
		}
	}

	public void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	public static void main(String[] args) {
		Solution s = new Solution();
		int[] nums = new int[] { 1, 5, 8, 0, 2 };
		int target = 9;
		int[] result = s.twoSum(nums, target);
		for (int i = 0; i != result.length; i++) {
			System.out.print(result[i] + " ");
		}

	}
}