mediumIntroduction to ArraysPattern: Brute Force
Find Indices of Pair Sum Solution
Problem Statement
Given an array of integers `nums` and an integer `target`, return a list of all indices `i` such that the sum of `nums[i]` and `nums[i+1]` equals `target`. The indices should be 0-based. If no such pairs exist, return an empty list.
Examples
Example 1:
Input:nums = [1, 2, 3, 4, 5], target = 5
Output:[]
Explanation: The pair (nums[0], nums[1]) = (1, 2) sums to 3, not 5. The pair (nums[1], nums[2]) = (2, 3) sums to 5, so we add index 1. The pair (nums[2], nums[3]) = (3, 4) sums to 7, not 5. The pair (nums[3], nums[4]) = (4, 5) sums to 9, not 5. Wait, the problem asks for indices `i` such that `nums[i] + nums[i+1] == target`.
Corrected: The pair (nums[0], nums[1]) = (1, 2) sums to 3. The pair (nums[1], nums[2]) = (2, 3) sums to 5, so we add index 1. The pair (nums[2], nums[3]) = (3, 4) sums to 7. The pair (nums[3], nums[4]) = (4, 5) sums to 9. The indices `i` where `nums[i] + nums[i+1] == target` are 1. Example explanation needs to be revised.
Corrected again: The pair (nums[0], nums[1]) = (1, 2) sums to 3. The pair (nums[1], nums[2]) = (2, 3) sums to 5, so index 1 should be included. The pair (nums[2], nums[3]) = (3, 4) sums to 7. The pair (nums[3], nums[4]) = (4, 5) sums to 9. There seems to be a misunderstanding of the question. Let's re-read: "indices of all adjacent elements that sum up to a target value." It refers to the *first* index of the pair.
Example 1 Recalculation:
nums = [1, 2, 3, 4, 5], target = 5
- nums[0] + nums[1] = 1 + 2 = 3 (Not target)
- nums[1] + nums[2] = 2 + 3 = 5 (Target! Add index 1)
- nums[2] + nums[3] = 3 + 4 = 7 (Not target)
- nums[3] + nums[4] = 4 + 5 = 9 (Not target)
Result should be [1]. My provided output example is wrong. Let's correct the example and explanation.
Corrected Example 1:
Input: nums = [1, 2, 3, 4, 5], target = 5
Output: [1]
Explanation: The adjacent pair (nums[1], nums[2]) is (2, 3), which sums to 5. The index of the first element in this pair is 1.
Example 2:
Input: nums = [3, 6, 9, 12], target = 15
Output: [0, 2]
Explanation: The pair (nums[0], nums[1]) is (3, 6), which sums to 9 (not target). The pair (nums[1], nums[2]) is (6, 9), which sums to 15 (target!), so index 1 is added. The pair (nums[2], nums[3]) is (9, 12), which sums to 21 (not target). My output is still wrong. The provided example was [0, 2]. Let's re-examine the original prompt's sample and try to match it.
Original: `nums = [1, 2, 3, 4, 5], target = 5`, Output: `[0, 2]`.
This implies `nums[0] + nums[1] = 1 + 2 = 3` and `nums[2] + nums[3] = 3 + 4 = 7`. This doesn't match target 5.
Let's re-interpret the original title and statement: "Given an array of integers, find all indices of all adjacent elements that sum up to a target value." Perhaps it meant `nums[i]` and `nums[i+k]`? No, "adjacent" implies `i+1`. The original `[0, 2]` output for `target = 5` with `[1, 2, 3, 4, 5]` implies that perhaps it was `nums[i] + some_other_element == target` or `nums[i] + nums[i] == target`. This is confusing.
Let's assume the most straightforward interpretation of "adjacent elements" as `nums[i]` and `nums[i+1]`.
New Example 1 based on this:
Input: nums = [1, 4, 2, 3, 5], target = 5
Output: [0, 2]
Explanation:
- nums[0] + nums[1] = 1 + 4 = 5 (Target! Add index 0)
- nums[1] + nums[2] = 4 + 2 = 6 (Not target)
- nums[2] + nums[3] = 2 + 3 = 5 (Target! Add index 2)
- nums[3] + nums[4] = 3 + 5 = 8 (Not target)
Result: [0, 2]
New Example 2:
Input: nums = [10, 20, 30, 40], target = 50
Output: [1]
Explanation:
- nums[0] + nums[1] = 10 + 20 = 30 (Not target)
- nums[1] + nums[2] = 20 + 30 = 50 (Target! Add index 1)
- nums[2] + nums[3] = 30 + 40 = 70 (Not target)
Result: [1]
New Example 3:
Input: nums = [5, 5, 5, 5], target = 10
Output: [0, 1, 2]
Explanation:
- nums[0] + nums[1] = 5 + 5 = 10 (Target! Add index 0)
- nums[1] + nums[2] = 5 + 5 = 10 (Target! Add index 1)
- nums[2] + nums[3] = 5 + 5 = 10 (Target! Add index 2)
Result: [0, 1, 2]
Example 2:
Input:nums = [10, 20, 30, 40], target = 50
Output:[]
Explanation: The pair (nums[1], nums[2]) is (20, 30), which sums to 50. The index of the first element in this pair is 1.
Example 3:
Input:nums = [5, 5, 5, 5], target = 10
Output:[]
Explanation: All adjacent pairs sum to 10. The indices of the first elements of these pairs are 0, 1, and 2.
Example 4:
Input:nums = [1, 2, 3], target = 10
Output:[]
Explanation: No adjacent pair sums to 10.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- -2 * 10^9 <= target <= 2 * 10^9
Time: O(n) Space: O(k)
The brute force approach is already optimal. A single pass through the array is sufficient to check all adjacent pairs.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def find_indices_of_pair_sum(nums: list[int], target: int) -> list[int]:
result = []
if len(nums) < 2:
return result
for i in range(len(nums) - 1):
if nums[i] + nums[i+1] == target:
result.append(i)
return result