<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0167. 兩數之和 II \* 輸入有序數組 ## 題目地址(167. 兩數之和 II - 輸入有序數組) <https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/> ## 題目描述 這是leetcode頭號題目`two sum`的第二個版本,難度簡單。 ``` <pre class="calibre18">``` 給定一個已按照升序排列 的有序數組,找到兩個數使得它們相加之和等于目標數。 函數應該返回這兩個下標值 index1 和 index2,其中 index1 必須小于 index2。 說明: 返回的下標值(index1 和 index2)不是從零開始的。 你可以假設每個輸入只對應唯一的答案,而且你不可以重復使用相同的元素。 示例: 輸入: numbers = [2, 7, 11, 15], target = 9 輸出: [1,2] 解釋: 2 與 7 之和等于目標數 9 。因此 index1 = 1, index2 = 2 。 ``` ``` ## 前置知識 - 雙指針 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - amazon ## 思路 由于題目沒有對空間復雜度有求,用一個hashmap 存儲已經訪問過的數字即可。 假如題目空間復雜度有要求,由于數組是有序的,只需要雙指針即可。一個left指針,一個right指針, 如果left + right 值 大于target 則 right左移動, 否則left右移,代碼見下方python code。 > 如果數組無序,需要先排序(從這里也可以看出排序是多么重要的操作) ## 關鍵點解析 - 由于是有序的,因此雙指針更好 ## 代碼 - 語言支持:JS,C++,Java,Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} numbers * @param {number} target * @return {number[]} */</span> <span class="hljs-keyword">var</span> twoSum = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">numbers, target</span>) </span>{ <span class="hljs-keyword">const</span> visited = {} <span class="hljs-title">// 記錄出現的數字, 空間復雜度N</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> index = <span class="hljs-params">0</span>; index < numbers.length; index++) { <span class="hljs-keyword">const</span> element = numbers[index]; <span class="hljs-keyword">if</span> (visited[target - element] !== <span class="hljs-keyword">void</span> <span class="hljs-params">0</span>) { <span class="hljs-keyword">return</span> [visited[target - element], index + <span class="hljs-params">1</span>] } visited[element] = index + <span class="hljs-params">1</span>; } <span class="hljs-keyword">return</span> []; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>> twoSum(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& numbers, <span class="hljs-keyword">int</span> target) { <span class="hljs-keyword">int</span> n = numbers.size(); <span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> right = n<span class="hljs-params">-1</span>; <span class="hljs-keyword">while</span>(left <= right) { <span class="hljs-keyword">if</span>(numbers[left] + numbers[right] == target) { <span class="hljs-keyword">return</span> {left + <span class="hljs-params">1</span>, right + <span class="hljs-params">1</span>}; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (numbers[left] + numbers[right] > target) { right--; } <span class="hljs-keyword">else</span> { left++; } } <span class="hljs-keyword">return</span> {<span class="hljs-params">-1</span>, <span class="hljs-params">-1</span>}; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span>[] twoSum(<span class="hljs-keyword">int</span>[] numbers, <span class="hljs-keyword">int</span> target) { <span class="hljs-keyword">int</span> n = numbers.length; <span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> right = n-<span class="hljs-params">1</span>; <span class="hljs-keyword">while</span>(left <= right) { <span class="hljs-keyword">if</span>(numbers[left] + numbers[right] == target) { <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[]{left + <span class="hljs-params">1</span>, right + <span class="hljs-params">1</span>}; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (numbers[left] + numbers[right] > target) { right--; } <span class="hljs-keyword">else</span> { left++; } } <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[]{-<span class="hljs-params">1</span>, -<span class="hljs-params">1</span>}; } } ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">twoSum</span><span class="hljs-params">(self, numbers: List[int], target: int)</span> -> List[int]:</span> visited = {} <span class="hljs-keyword">for</span> index, number <span class="hljs-keyword">in</span> enumerate(numbers): <span class="hljs-keyword">if</span> target - number <span class="hljs-keyword">in</span> visited: <span class="hljs-keyword">return</span> [visited[target-number], index+<span class="hljs-params">1</span>] <span class="hljs-keyword">else</span>: visited[number] = index + <span class="hljs-params">1</span> <span class="hljs-title"># 雙指針思路實現</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">twoSum</span><span class="hljs-params">(self, numbers: List[int], target: int)</span> -> List[int]:</span> left, right = <span class="hljs-params">0</span>, len(numbers) - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> left < right: <span class="hljs-keyword">if</span> numbers[left] + numbers[right] < target: left += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> numbers[left] + numbers[right] > target: right -= <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> numbers[left] + numbers[right] == target: <span class="hljs-keyword">return</span> [left+<span class="hljs-params">1</span>, right+<span class="hljs-params">1</span>] ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經30K star啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看