Given an array and a target, print the indices of two numbers that add up to the target, first with a brute-force double loop and then with a sorted two-pointer approach on a copy.
Solution
Main.java
import java.util.Arrays;
public class Main {
static int[] bruteForce(int[] a, int target) {
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++)
if (a[i] + a[j] == target) return new int[]{i, j};
return new int[0];
}
static int[] twoPointers(int[] a, int target) {
int[] s = a.clone();
Arrays.sort(s);
int lo = 0, hi = s.length - 1;
while (lo < hi) {
int sum = s[lo] + s[hi];
if (sum == target) return new int[]{s[lo], s[hi]};
if (sum < target) lo++; else hi--;
}
return new int[0];
}
public static void main(String[] args) {
int[] a = {8, 3, 11, 5, 15, 2};
for (int target : new int[]{13, 20, 100}) {
System.out.println(target + ": indices " + Arrays.toString(bruteForce(a, target))
+ ", values " + Arrays.toString(twoPointers(a, target)));
}
}
}
Output Verified by compiling and running
13: indices [0, 3], values [2, 11]
20: indices [3, 4], values [5, 15]
100: indices [], values []
Brute force is O(n²). After sorting, two pointers move inwards in O(n), but they report values, because sorting loses the original indexes (a HashMap solves both in O(n)).
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!