#백준_2143 두 배열의 합 - Java

# 유형 : 투포인터

# upper bound, lower bound 한가지 방법과 추가로 새롭게 hashMap 을 써서 풀어보았다.

배열 사이즈가 최대 1000이라서 n^2으로 합을 다 구하고 투포인터를 사용하면 된다.

package bj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
    static int N,M;
    static long T;
    static long arr_1[],arr_2[];
    static long cnt=0;
    static ArrayList<Long> arrList_1 = new ArrayList<>();
    static ArrayList<Long> arrList_2 = new ArrayList<>();
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Long.parseLong(br.readLine());
        N = Integer.parseInt(br.readLine());
        arr_1 = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
            arr_1[i] = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine());
        arr_2 = new long[M];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) 
            arr_2[i] = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<N; i++) {
            long sum = 0;
            for(int j=i; j<N; j++) {
                sum += arr_1[j];
                arrList_1.add(sum);
            }
        }
        for(int i=0; i<M; i++) {
            long sum = 0;
            for(int j=i; j<M; j++) {
                sum += arr_2[j];
                arrList_2.add(sum);
            }
        }
        Collections.sort(arrList_1);
        Collections.sort(arrList_2);
        
        int left = 0;
        int right = arrList_2.size()-1;
        
        for(int i=0; i<arrList_1.size(); i++) {
            long val = T-arrList_1.get(i);
            cnt += upper_bound(0, arrList_2.size(), val) - lower_bound(0, arrList_2.size(), val);
        }
        
        System.out.println(cnt);
    }
    public static int lower_bound(int left, int right, long target) {
        while(left<right) {
            int middle=(left+right)/2;
            if(arrList_2.get(middle) < target) {
                left = middle + 1;
            }else {
                right = middle;
            }
        }
        return right;
    }
    public static int upper_bound(int left, int right, long target) {
        while(left<right) {
            int middle=(left+right)/2;
            if(arrList_2.get(middle) <= target) {
                left = middle + 1;
            }else {
                right = middle;
            }
        }
        return right;
    }
}
 
 

 

 

package bj;
 
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class Main {
    static int N,M;
    static long T;
    static long arr_1[],arr_2[];
    static long cnt=0;
    static ArrayList<Long> arrList_1 = new ArrayList<>();
    static ArrayList<Long> arrList_2 = new ArrayList<>();
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Long.parseLong(br.readLine());
        N = Integer.parseInt(br.readLine());
        arr_1 = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
            arr_1[i] = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine());
        arr_2 = new long[M];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) 
            arr_2[i] = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<N; i++) {
            long sum = 0;
            for(int j=i; j<N; j++) {
                sum += arr_1[j];
                arrList_1.add(sum);
            }
        }
        for(int i=0; i<M; i++) {
            long sum = 0;
            for(int j=i; j<M; j++) {
                sum += arr_2[j];
                arrList_2.add(sum);
            }
        }
        Collections.sort(arrList_1);
        Collections.sort(arrList_2);
        
        HashMap<Long, Integer> map = new HashMap<>();
        for(long i : arrList_1) {
            if(map.containsKey(i)) {
                map.put(i, map.get(i)+1);
            }else {
                map.put(i,1);
            }
        }
        for(long i : arrList_2) {
            if(map.containsKey(T-i)) {
                cnt += map.get(T-i);
            }
        }
        System.out.println(cnt);
    }
}