在有序数组中找和一定的两数

可以使用双指针法来解决这个问题，时间复杂度为 O(n)。

具体做法是：定义两个指针，一个指向数组的第一个元素，一个指向数组的最后一个元素。然后不断地移动指针，直到找到两个数的和等于目标值或者指针相遇为止。如果两个数的和小于目标值，就将左指针向右移动一位；如果两个数的和大于目标值，就将右指针向左移动一位；如果两个数的和等于目标值，就找到了答案。

以下是示例代码：

int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

相关问题

两个有序数组找到中位数

假设有两个有序数组 nums1 和 nums2，长度分别为 m 和 n。要求找到这两个数组的中位数，时间复杂度要求为 O(log(m+n))。

一种思路是利用归并排序的思想，将两个有序数组合并成一个有序数组，然后找到中位数。

具体步骤如下：

1. 初始化两个指针 i 和 j，分别指向 nums1 和 nums2 的起始位置。
2. 判断两个指针所指元素的大小关系，将较小的元素加入到一个新的数组中，并将指针向后移动一位。
3. 重复步骤 2，直到任意一个指针越界。
4. 判断剩余数组的长度，将剩余的元素加入到新的数组中。
5. 找到新数组的中位数，如果新数组长度为偶数，则取中间两个数的平均值，如果长度为奇数，则取中间的数。

代码实现如下：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    int total = m + n;
    vector<int> nums(total);

    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if (nums1[i] < nums2[j]) {
            nums[k++] = nums1[i++];
        } else {
            nums[k++] = nums2[j++];
        }
    }

    while (i < m) {
        nums[k++] = nums1[i++];
    }

    while (j < n) {
        nums[k++] = nums2[j++];
    }

    if (total % 2 == 0) {
        return (nums[total / 2 - 1] + nums[total / 2]) / 2.0;
    } else {
        return nums[total / 2];
    }
}

时间复杂度为 O(m+n)，不符合题目要求。可以使用二分查找的方法将时间复杂度优化到 O(log(m+n))。

具体思路如下：

1. 假设两个有序数组的长度分别为 m 和 n，将 nums1 分为两部分，前一部分包含 i 个元素，后一部分包含 m-i 个元素；将 nums2 分为两部分，前一部分包含 j 个元素，后一部分包含 n-j 个元素。
2. 如果中位数在两个数组的左半部分，那么 i 和 j 都需要向右移动；如果在右半部分，i 和 j 都需要向左移动；如果 i 和 j 恰好满足条件，则找到了中位数。
3. 不断重复步骤 2，直到找到中位数。

代码实现如下：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    if (m > n) {
        swap(nums1, nums2);
        swap(m, n);
    }

    int left = 0, right = m, halfLen = (m + n + 1) / 2;
    while (left <= right) {
        int i = (left + right) / 2;
        int j = halfLen - i;

        if (i < m && nums2[j-1] > nums1[i]) {
            left = i + 1;
        } else if (i > 0 && nums1[i-1] > nums2[j]) {
            right = i - 1;
        } else {
            int maxLeft = 0;
            if (i == 0) {
                maxLeft = nums2[j-1];
            } else if (j == 0) {
                maxLeft = nums1[i-1];
            } else {
                maxLeft = max(nums1[i-1], nums2[j-1]);
            }

            if ((m + n) % 2 == 1) {
                return maxLeft;
            }

            int minRight = 0;
            if (i == m) {
                minRight = nums2[j];
            } else if (j == n) {
                minRight = nums1[i];
            } else {
                minRight = min(nums1[i], nums2[j]);
            }

            return (maxLeft + minRight) / 2.0;
        }
    }

    return 0.0;
}

时间复杂度为 O(log(min(m,n)))。

Java两个有序数组的中位数

题目描述：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2，请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解题思路：

1. 将两个数组合并成一个数组，再对合并后的数组进行排序，找到中位数

时间复杂度为O(m+n)log(m+n)，不符合题目要求

2. 利用二分法查找

首先，我们可以理解中位数的定义：如果某个有序数组的长度是奇数，那么其中位数就是最中间那个元素，如果是偶数，那么就是最中间两个元素的平均值。

在本题中，我们需要找到两个有序数组 A 和 B 的中位数，我们可以考虑从中位数的定义入手。如果我们能够将两个数组分别分成两部分，并且使得左半部分和右半部分分别满足以下两个条件：

1.左半部分的所有元素都小于右半部分的所有元素。

2.左半部分和右半部分分别包含了 A 和 B 数组的一半元素。

那么中位数就可以通过以下公式得到：

median = max(left_part) (len(A) + len(B) 为偶数)
median = (max(left_part) + min(right_part))/2 (len(A) + len(B) 为奇数)

为了使得划分满足上述两个条件，我们可以对较短的那个数组进行二分查找，然后根据查找到的位置将两个数组进行划分，最后再根据上述公式计算中位数。

具体实现见代码。

Java代码：

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

//确保nums1比nums2短
if (m > n) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tmp = m;
m = n;
n = tmp;
}

int iMin = 0, iMax = m;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = (m + n + 1) / 2 - i;
if (i < iMax && nums2[j - 1] > nums1[i]) {
iMin = i + 1;
} else if (i > iMin && nums1[i - 1] > nums2[j]) {
iMax = i - 1;
} else {
int maxLeft = 0;
if (i == 0) {
maxLeft = nums2[j - 1];
} else if (j == 0) {
maxLeft = nums1[i - 1];
} else {
maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
}

if ((m + n) % 2 == 1) {
return maxLeft;
}

int minRight = 0;
if (i == m) {
minRight = nums2[j];
} else if (j == n) {
minRight = nums1[i];
} else {
minRight = Math.min(nums1[i], nums2[j]);
}

return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}