讨论/《数组类算法》 - 两数之和 II - 输入有序数组/
《数组类算法》 - 两数之和 II - 输入有序数组
共 16 个回复
/* 通过二分法查找target - numbers[i] */
int binarySearch(int *numbers, int value, int low, int high) {
    int mid,lo = low, hi = high;
    while (lo < hi) {
        mid = (lo + hi) >> 1;
        (value < numbers[mid]) ? (hi = mid) : (lo = mid + 1);
    }
    return --lo ;
 }
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
    int i, j, k;
    int *retIndex;
    if (numbersSize < 2 || numbers == NULL) {
        return NULL;
    }
    retIndex = (int*)malloc(2*sizeof(int));
    if (retIndex == NULL) {
        return NULL;
    }
    for (i = 0; i < numbersSize - 1; i++) {
        k = target - numbers[i];
        j = binarySearch(numbers, k, i, numbersSize);
        if (numbers[j] == k) {
            retIndex[0] = i + 1;
            retIndex[1] = j + 1;
            *returnSize = 2;
            return retIndex;
        }
    }
    return NULL;
}

/* 双指针算法 */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
    int i, j, k;
    int *retIndex;
    if (numbersSize < 2 || numbers == NULL) {
        return NULL;
    }
    retIndex = (int*)malloc(2*sizeof(int));
    if (retIndex == NULL) {
        return NULL;
    }
    i = 0;
    j = numbersSize - 1;
    while (i < j) {
        k = numbers[i] + numbers[j];
        if (k < target) {
            i++;
        } else if (k > target) {
            j--;
        } else {
            retIndex[0] = i + 1;
            retIndex[1] = j + 1;
            *returnSize = 2;
            return retIndex;
        }
    }
    return NULL;
}
1
/*双指针*/
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i =0, j = numbers.size()-1;
        while(i<j){
            if((numbers[i]+numbers[j])== target) return {i+1, j+1};
            else if((numbers[i]+numbers[j])> target) j--;
            else i++;
        }
        return {-1,-1};
    }
};

/*二分法*/
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i = 0; i < numbers.size() - 1; i++ ){
            int low = i + 1 , high = numbers.size()-1;
            while(low <= high){
                int mid = (low + high) / 2;
                if((target - numbers[i]) == numbers[mid]){
                    return {i+1, mid+1};
                }
                else if((target - numbers[i]) > numbers[mid]){
                    low = mid + 1;
                }
                else{
                    high = mid - 1;
                }
            }
            
        }
        return {-1, -1};
    }
};

二分查找解法

class Solution {
    public int[] twoSum(int[] numbers, int target) {

        int[] ans = new int[] {-1, -1};

        for(int i = 0; i < numbers.length - 1; i++) {
            int j = binarySearch(numbers, i + 1, numbers.length - 1, target - numbers[i]);
            if(j != -1) {
                ans[0] = i + 1;
                ans[1] = j + 1;
            }
        }
        return ans;
    }

    public int binarySearch(int[] nums, int left, int right, int target) {

        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

C++双指针版本
思路:利用数组是有序这一特征,部署两个指针分别指向数组头和尾,两个指针指向的元素相加,大于target则尾指针-1,小于target则头指针+1.如果数组中有相加为target的成员,则必定能在时间复杂度为o(n)之内找到。

        int i=0;
        int j= numbers.size()-1;
        int sum=0;

        while(i<j){
            sum= numbers[i]+numbers[j];
            if(sum==target)return {i+1, j+1};
            sum>target?j--:i++; 
        }

        return {};
    #双指针
    # p0 = 0
    # p1 = len(numbers)-1

    # while p0 < p1:
    #     if numbers[p0] + numbers[p1] == target:
    #         return [p0 + 1, p1 + 1]
    #     elif numbers[p0] + numbers[p1] > target:
    #         p1 -= 1
    #     else:
    #         p0 += 1

    # 暴力循环
    # for i in range(len(numbers)-1):
    #     for j in range(i + 1, len(numbers)):
    #         if numbers[i] + numbers[j] == target:
    #             return [i+1, j+1]

    # 二分查找
    n = len(numbers)
    for i in range(n-1):
        low, high = i + 1, n - 1
        while low <= high:
            mid = (low + high) // 2
            if numbers[i] + numbers[mid] == target:
                return [i+1, mid+1]
            elif numbers[i] + numbers[mid] > target:
                high = mid - 1
            else:
                low = mid + 1
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] a = new int[2];
        if (numbers.length<2) {
            return a;
        }
        int m = numbers.length-1;
        int n=0;
        while (n<m) {
            if (numbers[n] + numbers[m] == target) {
                a[0]=n+1;
                a[1]=m+1;
                return a;
            } else if (numbers[n] + numbers[m] > target) {
                m--;
            } else {
                n++;
            }
        }
        return a;
    }
}
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
         int l = 0 , r = numbers.length - 1;
         while (l < r)
         {
             while (l < r && ((numbers[l] + numbers[r]) > target ))
             {
                 r--;
             }
             while (l < r && ((numbers[l] + numbers[r]) < target ))
             {
                 l++;
             }
             if (target == (numbers[l] + numbers[r]))
             {
                 break;
             }
         }

           result[0] = l + 1;
           result[1] = r + 1;
         return result;
    }
}
1
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> vec;
        int l = 0,r = numbers.size()-1;
        for(;l<r;)
        {
            if(numbers[l]+numbers[r]>target){
                r--;
                continue;
            }   
            if(numbers[l]+numbers[r]<target)
            {
                l++;
                continue;
            }
            else
            {
                vec.push_back(l+1);
                vec.push_back(r+1);
                break;
            }
        }
        return vec;
    }
};

image.png

func twoSum(numbers []int, target int) []int {
    m := make(map[int]int)
	var num []int
	for k1, v1 := range numbers {
		m[v1] = k1 + 1
	}
	for k2, v2 := range numbers {
		if m[target-v2] > 0 {
			num = []int{m[target-v2], k2 + 1}
            if k2+1 < m[target-v2] {
				num = []int{k2 + 1, m[target-v2]}
			}
            return num
		}
	}
	return num
}

image.png

双循环也能过,太丢人就不贴了