(Легкий вопрос LeetCode)

Учитывая массив nums. Мы определяем текущую сумму массива как runningSum[i] = sum(nums[0]…nums[i]).

Вернуть текущую сумму nums.

Пример 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Пример 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Пример 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

Ограничения:

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6

Теперь давайте сначала обсудим, что вы подразумеваете под текущей суммой?

Например, давайте сначала возьмем пример, nums = [1,2,3], и давайте использовать другой вектор an для хранения результатов.

Таким образом, первый элемент остается таким же, поэтому ans[0] = nums[0], но для следующего элемента ans[1] = nums[0]+nums[1] , ans[2] = nums[0]+nums[ 1]+nums[2] и так далее… Надеюсь, вы уже поняли концепцию.

Существуют различные подходы, с помощью которых можно решить этот вопрос. Давайте посмотрим, как выглядит решение грубой силы:

Подход грубой силы

Здесь я буду использовать другой вектор для хранения ответов, что означает, что я использую дополнительное пространство O (n), поскольку я буду проходить через массив, временная сложность также будет равна O (n). Но возникает вопрос, как я буду рассчитывать текущую сумму? Он прост и заключается в следующем.

Прежде всего, ans[0] = nums[0], что верно только для первого элемента, поэтому я уже скопировал весь массив nums в свой массив ans, поэтому, кроме первого элемента, я переопределю все остальные элементы, присутствующие в ans множество.

ans[1] = ans[0] + nums[1] , это отношение, которое оно будет иметь. объясню почему? Как мы видели выше, нам требуется предыдущий элемент для непрерывной суммы, поскольку формула выглядит как a[m] = a[0]+a[1]+…+a[m].

ans[2] = ans[1]+nums[2] , что означает, что здесь ans[1] = ans[0]+ans[1] из приведенного выше, поэтому ans[2] = ans[0]+ans[ 1]+числа[2]. Я надеюсь, что это проясняет, почему я использую приведенную выше формулу, nums[2] представляет второй элемент, а ans[1] представляет собой текущую сумму от индекса 0 до 1. Вот и весь подход к кодированию этого решения.

Поэтому и временная сложность, и пространственная сложность равны O(n) только при использовании описанного выше подхода.

Теперь давайте проверим, используя концепцию, о которой мы подумали, а позже закодируем ее.

числа=[1,2,3,4] , ответы = [1,2,3,4]

ans[1] = ans[0] + nums[1] = 1 + 2 = 3 ; ответ = [1,3,3,4]

ans[2] = ans[1]+ nums[2] = 3 + 3 = 6 ; ответ = [1,3,6,4]

ans[3] = ans[2] + nums[3] = 6 + 4 = 10 ; ответ = [1,3,6,10]

Итак, теперь наш окончательный ответ становится ans = [1,3,6,10]

Теперь код:

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        // brute force approach 
        // tc - O(n) & sc - O(n)
        vector<int>ans;
        ans = nums;
        for(int i=1;i<nums.size();i++)
        {
            ans[i] = ans[i-1]+nums[i];
        }
        return ans;
    }
};

Итак, теперь я надеюсь, что это ясно для вас. Попробуйте повторить, используя еще несколько примеров, если вы не можете ясно понять.

Оптимизированный подход

Как же должен выглядеть оптимизированный подход? Есть идеи? Ну, я думаю, мы можем уменьшить сложность пространства, что скажешь? Можем ли мы сделать сложность пространства постоянной, то есть O (1), возможно ли это? Я думаю, да, это так. Давайте посмотрим, как ниже:

Взяв тот же пример: nums = [1,2,3,4]

так что nums[0] остается прежним, как насчет следующего элемента?

числа [1] = числа [0] + числа [1] = 1 + 2 = 3 ; числа = [1,3,3,4]

числа [2] = числа [1] + числа [2] = 3 + 3 = 6 ; числа = [1,3,6,4]

числа [3] = числа [2] + числа [3] = 6 + 4 = 10 ; числа = [1,3,6,10]

и это наш окончательный ответ. Но как сформулировать наш ответ в терминах i при переборе массива, это просто, для каждого i мы должны найти элемент с i-м и (i-1)-м индексом, поэтому nums[i] = nums [i-1]+nums[i], где i≥1.

Кажется довольно легко, верно? Как только вы поймете концепцию, все вопросы покажутся вам проще. Теперь давайте закодируем его:

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        for(int i=1;i<nums.size();i++)
        {
            nums[i]=nums[i-1]+nums[i];
        }
        return nums;
    }
};

Таким образом, наша временная сложность – O(n), а пространственная – O(1).

Надеемся, что эта статья поможет вам четко понять концепции. А до тех пор продолжайте программировать и решать, потому что последовательность всегда является ключом к достижению целей в жизни! Удачи 🙌💻

Поскольку вам понравилось читать мой блог, почему бы не купить мне кофе и не поддержать мою работу здесь!! https://www.buymeacoffee.com/sukanyabharati ☕