查找升序排序数组中满足指定正向差值范围的所有索引

Hey there! Let's figure out how to optimize this problem since the naive approach of checking every subsequent element for each index is O(n²)—which gets pretty slow once your array grows large. Since the array is sorted in ascending order, we can leverage this property to cut down the time complexity significantly.

Approach 1: Two Pointers (O(n) Time Complexity) #

The sorted nature lets us use two pointers that only move forward, avoiding redundant checks. Here's the core idea:

• For each index i, maintain a left pointer that finds the first j > i where a[j] - a[i] >= x.
• Maintain a right pointer that finds the first j > i where a[j] - a[i] > y.
• If left < right, there's at least one valid j (between left and right-1) that satisfies the condition, so mark i as True.

Since both pointers only move right as i increases, each element is processed at most twice—leading to linear time complexity, which is the most efficient possible for this problem.

Code Example (Python):

def find_valid_indices(a, x, y):
    n = len(a)
    result = [False] * n
    left = 1
    right = 1
    
    for i in range(n):
        # Move left to the first j > i where a[j] - a[i] >= x
        while left < n and a[left] - a[i] < x:
            left += 1
        # Move right to the first j > i where a[j] - a[i] > y
        while right < n and a[right] - a[i] <= y:
            right += 1
        # Check if there's any valid j in [left, right-1]
        if left < right:
            result[i] = True
    
    return result

Approach 2: Binary Search (O(n log n) Time Complexity) #

If you prefer a more straightforward implementation that's easier to reason about, binary search works great here. For each i, we can:

• Use binary search to find the smallest j > i where a[j] >= a[i] + x.
• Use binary search to find the largest j > i where a[j] <= a[i] + y.
• If the smallest valid j is <= the largest valid j, then i is a valid index.

This approach trades a tiny bit of speed for readability, and it's still efficient enough for most practical use cases.

Code Example (Python):

import bisect

def find_valid_indices(a, x, y):
    n = len(a)
    result = [False] * n
    
    for i in range(n - 1):  # Last element has no j > i, so stays False
        target_low = a[i] + x
        target_high = a[i] + y
        
        # Find first index >= target_low, starting from i+1
        left_idx = bisect.bisect_left(a, target_low, i + 1, n)
        # Find first index > target_high, subtract 1 to get the last valid j
        right_idx = bisect.bisect_right(a, target_high, i + 1, n) - 1
        
        if left_idx <= right_idx:
            result[i] = True
    
    return result

Edge Cases to Keep in Mind #

• Arrays with length < 2: All values in the result array will be False (no j > i exists to form a positive difference).
• x == y: We're checking if any j > i has a[j] - a[i] exactly equal to x—both approaches handle this naturally.
• Duplicate elements: Since the array is sorted, both two pointers and binary search correctly account for duplicates without extra logic.

内容的提问来源于stack exchange，提问作者AsaridBeck91