力扣1590. 使數組和能被 P 整除

在這里插入圖片描述
在這里插入圖片描述

這一題的難點在于模運算,對模運算足夠了解,對式子進行變換就很容易得到結果,本質上還是一道前綴和+哈希表的題
這里重點講一下模運算。
常見的模運算的用法
(a-b)%k==0等價于 a%k=b%k
而在這一題中由于多了一個len,(數組的總和)即 len-(sum[j]-sum[i])%p=0
len%p=(sum[j]-sum[i])%p
因為兩邊都是%p
所以可以把%p提出來,對等式進行移項
(sum[j]-len)%p=sum[i]%p
而減法的模運算:
(a?b)%p=((a%p)?(b%p)+p)%p
也就是 ((sum[j]%p)-(len%p)+p)%p=sum[i]%p

加法的模運算和乘法的模運算都是同理
進行多次%p的原因是為了避免負數,就這一題我們可以知道的是sum[j]-len一定是小于0的
當弄清楚模運算后代碼就好寫了

class Solution {
public:long long sum[100005];
unordered_map<int,int> mp;int minSubarray(vector<int>& nums, int p) {for(int i=0;i<nums.size();i++){sum[i+1]=sum[i]+nums[i];}long long len=sum[nums.size()];//(len-(sum[j]-sum[i]))%k==0;// len%k==(sum[j]-sum[i])%k//s[right]- s[left]≡x(modp)//((s[right]-x)modp+p)modp=s[left]modp//(a+b)%k==0//a%k==b%kif(len%p==0){return 0;}mp[0]=0;int ans=INT_MAX;for(int j=0;j<nums.size();j++){if(mp.count((sum[j+1]%p-len%p+p)%p)){int i=mp[(sum[j+1]%p-len%p+p)%p]; ans=min(ans,j+1-i);} 	mp[sum[j+1]%p]=j+1;} if(ans==INT_MAX||ans==nums.size()){return -1;}else{return ans;}}
};

要注意的是如果本身數組和%p就已經滿足條件,那么就不用除去子數組,提前返回0
,如果移除的數組和是原數組和本身或者不存在符合條件的情況,那么都return -1
最后
時間復雜度O(n);

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/pingmian/86801.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/86801.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/86801.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

FPGA內部資源介紹

FPGA內部資源介紹 目錄 邏輯資源塊LUT&#xff08;查找表&#xff09;加法器寄存器MUX&#xff08;復用器&#xff09;時鐘網絡資源 全局時鐘網絡資源區域時鐘網絡資源IO時鐘網絡資源 時鐘處理單元BLOCK RAMDSP布線資源接口資源 用戶IO資源專用高速接口資源 總結 1. 邏輯資源…

CSS 列表

CSS 列表 引言 CSS 列表是網頁設計中常用的一種布局方式&#xff0c;它能夠幫助我們以更靈活、更美觀的方式展示數據。本文將詳細介紹 CSS 列表的創建、樣式設置以及常用技巧&#xff0c;幫助您更好地掌握這一重要技能。 CSS 列表概述 CSS 列表主要包括兩種類型&#xff1a…

spring中的@Cacheable緩存

1. 使用方法 在方法上面加上注解Cacheable&#xff0c; OverrideCacheable(cacheNames "userCache", key "#id")public User getUserById(Long id) {System.out.println("查詢數據庫了");return getById(id);}如果你的項目中引入了&#xff…

Node.js特訓專欄-實戰進階:9.MySQL連接池配置與優化

?? 歡迎來到 Node.js 實戰專欄!在這里,每一行代碼都是解鎖高性能應用的鑰匙,讓我們一起開啟 Node.js 的奇妙開發之旅! Node.js 特訓專欄主頁 專欄內容規劃詳情 MySQL連接池配置與優化:提升數據庫交互性能的關鍵 一、MySQL連接池基礎概念 1.1 什么是連接池? 連接池是…

【innovus基礎】- 如何手動畫線?

后端實現的過程就是將邏輯連線變為物理的金屬連線的過程。 1、打開Pin shape的Visible 和 Selected開關&#xff0c;使其可見并可選 2、選中想要畫線的IOCell 3、鼠標選中對應的pin 4、使用dbGet 獲取此pin腳邏輯連線net的名字&#xff1b; dbGet selected.net.name 5、使用畫…

element-plus限制日期可選范圍(這里以7天為例)

element-plus日期范圍限制功能實現邏輯 1. 需求&#xff1a;通過限制時間的可選范圍減少請求的數據量 2. 實現效果&#xff1a; 日期選擇器做限制 3. 代碼邏輯&#xff1a; 思路&#xff1a;通過calendar-change獲取開始日期&#xff0c;然后通過disabled-date禁用不滿足條件…

機器學習2-梯度下降與反向傳播

損失函數 與 平均方差函數 傻傻分不清 損失函數是概念&#xff1b;平均方差函數是具體的實現 損失函數&#xff08;如均方誤差 MSE&#xff09;用于衡量模型預測值與真實值之間的差距。損失越小&#xff0c;說明模型對當前數據的擬合越好。 但模型并非擬合度越高越好&#xf…

安全生產風險管控平臺:企業安全管理的智能化解決方案

在工業生產、建筑施工、能源化工等領域&#xff0c;安全生產是企業可持續發展的基石。然而&#xff0c;傳統安全管理模式依賴人工巡檢、紙質記錄和事后處理&#xff0c;難以滿足現代化企業的高效風險管控需求。安全生產風險管控平臺應運而生&#xff0c;它利用物聯網、大數據、…

如何保證數據庫與 Redis 緩存的一致性?

在現代互聯網應用中&#xff0c;Redis 緩存幾乎是性能優化的標配。但在使用過程中&#xff0c;一個繞不過去的問題就是&#xff1a; 如何保證 Redis 緩存與數據庫之間的數據一致性&#xff1f; 特別是在高并發場景下&#xff0c;讀寫操作錯位可能導致緩存中出現臟數據&#xff…

現代 JavaScript (ES6+) 入門到實戰(三):字符串與對象的魔法升級—模板字符串/結構賦值/展開運算符

在前兩篇&#xff0c;我們升級了變量和函數。今天&#xff0c;我們要給 JavaScript 中最常用的兩種數據類型——字符串&#xff08;String&#xff09;和對象&#xff08;Object&#xff09;——裝備上 ES6 帶來的強大魔法。 準備好告別丑陋的 號拼接和重復的對象屬性賦值了嗎…

GitLab 備份恢復與配置遷移詳盡教程(實戰版)

&#x1f6e0; GitLab 備份恢復與配置遷移詳盡教程&#xff08;實戰版&#xff09; &#x1f9f1; 一、環境準備 1.1 檢查版本一致性 恢復目標機 GitLab 版本必須與備份文件所用版本一致或兼容&#xff08;推薦相同版本&#xff09; 查看當前 GitLab 版本&#xff1a; sudo g…

英飛凌高性能BMS解決方案助力汽車電動化

隨著電動汽車越來越被大眾接受&#xff0c;車輛電氣化、智能化程度越來越高&#xff0c;如何提高電動汽車的續航里程&#xff0c;同時保障車輛安全可靠持久運行是當前最主要的技術難題之一。而先進的電池管理系統 (BMS)有助于克服電動汽車廣泛普及的關鍵障礙&#xff1a;續航里…

react + ant-design實現數字對比動畫效果:當新獲取的數字比之前展示的數字多或少2時,顯示“+2”或“-2”的動畫效果

react ant-design實現數字對比動畫效果&#xff1a;當新獲取的數字比之前展示的數字多或少2時&#xff0c;顯示“2”或“-2”的動畫效果 1. 創建獨立的 AnimatedValue 組件 // components/AnimatedValue/index.jsx import React, { useState, useEffect, useRef } from reac…

自動化測試--Appium和ADB及常用指令

1.Appium Appium工具庫&#xff1a; appium server&#xff1a;服務器&#xff08;類似于瀏覽器的驅動&#xff09;&#xff0c;核心進行客戶端命令的接受&#xff0c;完成設備的自動化指令 appium client&#xff1a;客戶端&#xff0c;讓代碼進行調用&#xff0c;發送自動化的…

2025.6.29總結

有一點我很好奇&#xff0c;工作后&#xff0c;我該拿什么去衡量自己的進步呢&#xff1f; 在我的大學四年&#xff0c;確實有個量化的標準&#xff0c;讀了多少本書&#xff0c;寫了多少篇總結&#xff0c;多少篇技術博客&#xff0c;多少行代碼&#xff0c;運動了多少公里&a…

Docker 部署 Kong云原生API網關

Docker 部署 Kong云原生API網關 本指南提供了在 Docker Compose 上配置 Kong Gateway 的步驟&#xff0c;基于有數據庫模式的配置。本指南中使用的數據庫是 PostgreSQL。 前置條件 準備一臺Ubuntu服務器&#xff1a; 節點IP: 192.168.73.11操作系統&#xff1a; Ubuntu 24…

深度剖析 Apache Pulsar:架構、優勢與選型指南

Apache Pulsar 是一款云原生分布式消息流平臺&#xff0c;融合了消息隊列、流處理和存儲能力&#xff0c;采用獨特的“存儲計算分離”架構&#xff08;Broker 無狀態 BookKeeper 持久化存儲&#xff09;。以下從核心特性、對比優勢及適用場景展開分析&#xff1a; 一、Pulsar…

java 導出word 實現循環表格

如果是固定的值 用 {{}} 即可 但是如果是循環表格&#xff0c;那么就需要制定模板為如圖 然后在處理表格數據時候&#xff1a; /*** 傳入 節點對象 返回生成的word文檔* param flangeJoint* return* throws IOException*/private XWPFTemplate getXwpfTemplate(CmComplaintEn…

XIP (eXecute In Place)

NOR Flash 能直接執行代碼(XIP)而 NAND Flash 不能,根本原因在于它們的物理結構和訪問接口存在本質區別。下面用技術原理 + 現實比喻幫你徹底理解: 1. XIP 是什么? XIP (eXecute In Place) 指代碼不需要從存儲介質復制到 RAM,而是 CPU 直接從存儲介質(如 Flash)中讀取…

【android bluetooth 協議分析 10】【AVRCP詳解1】【PlaybackStateCompat類如何查看】

1. 問題 android/app/src/com/android/bluetooth/avrcpcontroller/AvrcpControllerService.java import android.support.v4.media.MediaBrowserCompat.MediaItem; import android.support.v4.media.session.PlaybackStateCompat;private int toPlaybackStateFromJni(int fro…