长沙住房建设部网站,沈阳方正建设监理网站,wordpress 国内主题 营销主题,西安网站制作资源目录7 两数之和题目描述#xff1a;解题思路与代码暴力解法#xff1a;解法一#xff1a;二分查找解法二#xff1a;双指针2 斐波那契数列题目描述#xff1a;解题思路与代码解法一解题思路与代码暴力解法解法一二分查找解法二双指针2 斐波那契数列题目描述解题思路与代码解法一暴力递归解法二去重递归解法三双指针迭代7 两数之和
题目描述
给定一个升序排列的整数数组 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存入maptarget - num作为key public int[] twoSum(int[] nums, int target) {MapInteger, Integer map new HashMapInteger, 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右指针指向数组tailheadtail 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[num1];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 i2; i num; i){int sum low high;low high;high sum;}return high;}
