leetcode01两数之和

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] + " ");
		}

	}
}