给定一个已经 按绝对值升序排列 的数组,找到两个数使他们加起来的和等于特定数。
函数应该返回这两个数的下标,index1必须小于index2。注意返回的值是0-based。
请使用双指针完成本题,否则你有可能会被取消比赛资格。
注意事项:
```
- 数据保证nums中的所有数的互不相同的。
- nums数组长度≤100000
- nums内的数≤1000000000
```
样例:
```
输入:
[0,-1,2,-3,4]
1
输出: [[1,2],[3,4]]
说明: nums[1] + nums[2] = -1 + 2 = 1,
nums[3] + nums[4] = -3 + 4 = 1
你也可以返回 [[3,4],[1,2]],
系统将自动帮你排序成 [[1,2],[3,4]]。
但是[[2,1],[3,4]]是不合法的。
```
挑战1: O(N)时间复杂度 + O(1)额外空间复杂度
挑战2: 不分类讨论
题目链接:https://www.lintcode.com/problem/two-sum-vii/description
LeetCode题解167.two-sum-ii-input-array-is-sorted题目地址 https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/ 题目描述 这是leetcode头号题目two sum的第二个版本,难度简单。 Given an array of integers that is already sorted in ascendi…
LeetCode题解113.path-sum-ii题目地址 https://leetcode.com/problems/path-sum-ii/description/ 题目描述 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. Note: A leaf…
LeetCode题解15.3-sum题目地址 https://leetcode.com/problems/3sum/description/ 题目描述 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in…
LeetCode题解124.binary-tree-maximum-path-sum题目地址 https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ 题目描述 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as a…
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。