1 两数之和
题目描述：
给定一个升序排列的整数数组 numbers ，从数组中找出两个数满足相加之和等于目标数 target 。
假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。
返回两数的下标值，以数组形式返回
解题思路与代码
暴力解法：
public int[] twoSum(int[] nums, int target) { int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[0]; }
时间复杂度：O(N的平方)
空间复杂度：O(1)
哈希表：将数组的值作为key存入map，target - num作为key
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; ++i) { if (map.containsKey(target - nums[i])) { return new int[]{map.get(target - nums[i]), i}; } map.put(nums[i], i); } return new int[0]; }
时间复杂度：O(N)
空间复杂度：O(N)
解法一：二分查找
先固定一个值(从下标0开始)，再用二分查找查另外一个值，找不到则固定值向右移动，继续二分查找
public int[] twoSearch(int[] numbers, int target) { for (int i = 0; i < numbers.length; ++i) { int low = i, high = numbers.length - 1; while (low <= high) { int mid = (high - low) / 2 + low; if (numbers[mid] == target - numbers[i]) { return new int[]{i, mid}; } else if (numbers[mid] > target - numbers[i]) { high = mid - 1; } else { low = mid + 1; } } } }
时间复杂度：O(N * logN)
空间复杂度：O(1)
解法二：双指针
左指针指向数组head，右指针指向数组tail，head+tail > target 则tail 左移，否则head右移
public int[] twoPoint(int[] numbers, int target) { int low = 0, high = numbers.length - 1; while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) { return new int[]{low + 1, high + 1}; } else if (sum < target) { ++low; } else { --high; } } return new int[]{-1, -1}; }
时间复杂度：O(N)
空间复杂度：O(1)
2 斐波那契数列
题目描述：
求取斐波那契数列第N位的值。
斐波那契数列：每一位的值等于他前两位数字之和。前两位固定
解题思路与代码 
解法一：暴力递归
public static int calculate(int num){ if(num == 0 ){ return 0; } if(num == 1){ return 1; } return calculate(num-1) + calculate(num-2); }
解法二：去重递归
递归得出具体数值之后、存储到一个集合(下标与数列下标一致)，后面递归之前先到该集合查询一次，如果查到则无需递归、直接取值。查不到再进行递归计算
public static int calculate2(int num){ int[] arr = new int[num+1]; return recurse(arr,num); } private static int recurse(int[] arr, int num) { if(num == 0 ){ return 0; } if(num == 1){ return 1; } if(arr[num] != 0){ return arr[num]; } arr[num] = recurse(arr,num-1) + recurse(arr,num-2); return arr[num]; }
解法三：双指针迭代
基于去重递归优化，集合没有必要保存每一个下标值，只需保存前两位即可，向后遍历，得出N的值
public static int iterate(int num){ if(num == 0 ){ return 0; } if(num == 1){ return 1; } int low = 0,high = 1; for(int i=2; i<= num; i++){ int sum = low + high; low = high; high = sum; } return high; }
