Leetcode-167. 两数之和 II - 输入有序数组

Dear 丶 2023-02-28 04:26 24阅读 0赞

### 167. 两数之和 II - 输入有序数组 ###

*  方法一：暴力破解
 *  方法二：二分查找
 *  方法三：双指针

> Leetcode-167. 两数之和 II - 输入有序数组  
> 链接：[https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/][https_leetcode-cn.com_problems_two-sum-ii-input-array-is-sorted]

# 方法一：暴力破解 #

**时间时间复杂度:O(n^2)**

class Solution { 
        public int[] twoSum(int[] numbers, int target) { 
            int a[]=new int[2];
            for(int i=0;i<numbers.length;i++){ 
                for(int j=i+1;j<numbers.length;j++){ 
                    if(numbers[i]+numbers[j]==target){ 
                        a[0]=i+1;
                        a[1]=j+1;
                    }
                }
            }
            return a;
        }
    }

# 方法二：二分查找 #

**时间时间复杂度:O(nlogn)**

class Solution { 
          public int[] twoSum(int[] numbers, int target) { 
            int a[]=new int[2];
            for(int i=0;i<numbers.length-1;i++){ 
                int left=i+1;
                int right=numbers.length-1;
                int mid=0;
                int temp = target - numbers[i];
                while(left<=right){        //这里的 = 非常重要，可以和方法三的双指针对比思考一下为什 
                    mid =(left+right)/2;  //么这里要用 = ，而方法三用或不用都行！！！！！！！！
                    if(numbers[mid] == temp){ 
                        a[0]=i+1;
                        a[1]=mid+1;
                        return a;
                    }else if(numbers[mid] <temp){ 
                        left=mid+1;
                    }else { 
                        right=mid-1;
                    }
                }
            }
    
            return a;
        }
    }

# 方法三：双指针 #

**时间时间复杂度:O(n)**

class Solution { 
          public int[] twoSum(int[] numbers, int target) { 
            int a[]=new int[2];
            int left=0;
            int right=numbers.length-1;
            while(left<=right){         //这里可以只<，=号多余可以去掉
                if(numbers[left]+numbers[right]==target){ 
                    a[0]=left+1;
                    a[1]=right+1;
                            return a;
                }else if(numbers[left]+numbers[right]<target){ 
                    left++;
                }else{ 
                    right--;
                }
            }
            return a;
        }
    }

--------------------

**持续更新中…**  
**文章参考学习地址：[https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/][https_leetcode-cn.com_problems_two-sum-ii-input-array-is-sorted]**

[https_leetcode-cn.com_problems_two-sum-ii-input-array-is-sorted]: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/