[leetcode 의 여행] 배열 - 888. 공평 한 사탕 교환

앨 리 스 와 밥 은 서로 다른 크기 의 사탕 봉 을 가지 고 있다. A[i] 앨 리 스 가 가 진 제  i  덩어리의 크기, B[j] 밥 이 가 진 1 등 이 야.  j  알사탕 크기.
그들 은 친구 이기 때문에 사탕 봉 을 교환 하려 고 한다. 이렇게 교환 한 후에 그들 은 모두 같은 사탕 의 총량 을 가지 고 있다.(한 사람 이 가 진 사탕 의 총량 은 그들 이 가 진 사탕 봉 크기 의 총화 이다.)
정수 배열 을 되 돌려 줍 니 다.  ans, 그 중  ans[0]  앨 리 스 가 교환 해 야 할 사탕 봉 의 크기 입 니 다. ans[1] 밥 이 교환 해 야 할 캔디 스틱 크기 입 니 다.
만약 여러 개의 답 이 있다 면, 너 는 그 중의 어떤 것 도 되 돌려 줄 수 있다.답 의 존 재 를 보증 하 다.
예시 1:
A = [1,1], B = [2,2]
[1,2]

예시 2:
A = [1,2], B = [2,3]
[1,2]

예시 3:
A = [2], B = [1,3]
[2,3]

예시 4:
A = [1,2,5], B = [2,4]
[5,4]

알림:
  • 1 <= A.length <= 10000
  • 1 <= B.length <= 10000
  • 1 <= A[i] <= 100000
  • 1 <= B[i] <= 100000
  • 앨 리 스 와 밥 의 사탕 총량 이 다르다 는 것 을 보증한다.
  • 답 은 분명히 존재 한다.

  • 해답:
      
    * A      sa,B      sb
    *  sa - x + y = sb - y + x
    *  y = x + (sb - sa ) / 2
    *         B       y ,       
    /**
     *   :
     * A      sa,B      sb
     *  sa - x + y = sb - y + x
     *  y = x + (sb - sa ) / 2
     *         B       y ,       
     * @param A
     * @param B
     * @return   
     */
    public static int[] fairCandySwap(int[] A, int[] B) {
        int middle = (sum(B, B.length) - sum(A, A.length)) / 2;
        Set setB = new HashSet<>();
        for (int x : B) setB.add(x);
        for (int x : A)
            if (setB.contains(x + middle))
                return new int[]{x,x + middle};
        return null;
    }

    좋은 웹페이지 즐겨찾기