【codility】Lesson 3: Time Complexity TapeEquilibrium

subject

与えられたN個の要素から成り立つ配列Aを前半の長さPと後半の長さ（N-P）に切断して差分を比較し、最も少ない差分値を返す問題。
例）
A = {3, 1, 2, 4, 3}が与えられた場合の返却値は1である。
P = 1, difference = |3 - 10| = 7 もう少し詳しく書くと、前半の配列Af = {3}と後半の配列Ab = {1, 2, 4, 3}のそれぞれの合計の差である。
同様に、下記も求めていく。
P = 2, difference = |4 - 9| = 5
P = 3, difference = |6 - 7| = 1
P = 4, difference = |10 - 3| = 7
P = 1~4の中で一番値の低いものを返却する。

submit

とても長い戦い。やっととれたscore100!!!

program

Point:あらかじめSUMを取っておくこと
前半の配列の和frontSumと、後半の配列の和backSumとそれぞれ和をもとめておくことで、１つの要素の移動だけでfront,backの和が計算でき、差を求めることができる。
今回、ネックだったのは要素はマイナスの値も含まれているところ。加えて、配列が２つの時のケースを場合分けするところだった。結構時間がかかってしまった。

tapeEquilibrium.cpp

#include<iostream>
#include<vector>
using namespace std;

int solution(vector<int> &A) {
    int frontSum = 0;
    int backSum = 0;
    int val = 0;

    if (!A.empty()) {
        if((int)A.size() == 2){
            return (abs(A[0] - A[1]));
        }
        frontSum = A[0];
        for (int i = 1; i < (int)A.size(); ++i) {
            backSum += A[i];
        }

        int min = abs(frontSum - backSum);
        for (int i = 1; i < ((int)A.size() - 1); ++i) {
            frontSum += A[i];
            backSum  -= A[i];
            val = abs(frontSum - backSum);
            if (val < min)
                min = val;
        }
        return min;
    }
    return 0;
}