You have two integer arrays, a and b, and an integer target value v. Determine whether there is a pair of numbers, where one number is taken from a and the other from b, that can be added together to get a sum of v. Return true if such a pair exists, otherwise return false.

Example

For a = [1, 2, 3], b = [10, 20, 30, 40], and v = 42, the output should be

solution(a, b, v) = true.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.integer a

  An array of integers.

  Guaranteed constraints:

  0 ≤ a.length ≤ 105,

  • 109 ≤ a[i] ≤ 109.

• [input] array.integer b

  An array of integers.

  Guaranteed constraints:

  0 ≤ b.length ≤ 105,

  • 109 ≤ b[i] ≤ 109.

• [input] integer v

  Guaranteed constraints:

  • 109 ≤ v ≤ 109.

• [output] boolean

  true if there are two elements from a and b which add up to v, and false otherwise.

풀이

boolean solution(long[] a, long[] b, long v) {
    if (a.length == 0 || b.length == 0) return false;
    
    int idx = a.length - 1;
    
    // Hidden Test 19 시간 초과로 인한 이분탐색
    for (int i = 0; i < a.length / 2; i ++) {
        long head = a[i];
        long tail = a[idx --];
        
        for (long l : b) {
            if (head + l == v) return true;
            if (tail + l == v) return true;
            if (a.length % 2 > 0 && i == (a.length / 2) - 1) {
                if (a[i + 1] + l == v) return true;
            }
        }
    }
    
    return false;
}