佛山建网站永网,陕西整站关键词自然排名优化,做糕点的网站,网站媒体作风建设年工作总结目录 1.题目2.题解解法一#xff1a;暴力枚举解法二#xff1a;哈希表解法解法三#xff1a;双指针(有序状态)解法四#xff1a;二分查找(有序状态) 1.题目 给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数… 目录 1.题目2.题解解法一暴力枚举解法二哈希表解法解法三双指针(有序状态)解法四二分查找(有序状态) 1.题目 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 示例1:
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2
输入nums [3,2,4], target 6
输出[1,2]示例 3
输入nums [3,3], target 6
输出[0,1]提示
2 nums.length 104
-109 nums[i] 109
-109 target 109
只会存在一个有效答案2.题解
解法一暴力枚举 最容易想到的方法是枚举数组中的每一个数 x寻找数组中是否存在 target - x。 当我们使用遍历整个数组的方式寻找 target - x 时需要注意到每一个位于 x 之前的元素都已经和 x 匹配过因此不需要再进行匹配。而每一个元素不能被使用两次所以我们只需要在 x 后面的元素中寻找 target - x。 public int[] TwoSum(int[] nums, int target){int nnums.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, 0 };}时间复杂度 O(n^2) 空间复杂度 O(1)
解法二哈希表解法 注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此我们需要一种更优秀的方法能够快速寻找数组中是否存在目标元素。如果存在我们需要找出它的索引。 使用哈希表可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。 这样我们创建一个哈希表对于每一个 x我们首先查询哈希表中是否存在 target - x然后将 x 插入到哈希表中即可保证不会让 x 和自己匹配。 public int[] TwoSum(int[] nums, int target) {Dictionaryint, int twoSum new Dictionaryint, int();for (int i 0; i nums.Length; i){if(twoSum.ContainsKey(target-nums[i])){return new int[] {twoSum[target - nums[i]], i};}else {twoSum[nums[i]] i;}}return new int[] {0, 0};}时间复杂度O(n)空间复杂度O(n)。
解法三双指针(有序状态) public int[] towSum(int[] nums, int target){int left 0;int right nums.Length - 1;for (int i 0; i nums.Length; i){if (nums[left] nums[right] target){right--;}else if (nums[left] nums[right] target){left;}else{return new int[] { left, right };}}return new int[] { };}时间复杂度O(nlogn)空间复杂度O(n)。
解法四二分查找(有序状态) public int[] towSum(int[] nums, int target){for (int i 0; i nums.Length; i){int low i 1;int high nums.Length - 1;while (low high){int mid (high - low) / 2 low;if (nums[mid] target - nums[i]){high mid - 1;}else if (nums[mid] target - nums[i]){low mid 1;}else{return new int[] { i, mid };}}}return new int[] { };}时间复杂度O(nlogn)空间复杂度O(n)。
